# Lowest Common Ancestor of a Binary Tree

Category

Binary Tree - DFS

Checkbox

Checkbox

Difficulty

Medium

Index

38

Key Ideas

The key idea to solve problem number 236, "Lowest Common Ancestor of a Binary Tree," is to perform a depth-first search (DFS) traversal of the binary tree to find the lowest common ancestor between two given nodes.

Problem Number

236

Problem Summary

**Problem Summary:**The "Lowest Common Ancestor of a Binary Tree" problem asks you to find the lowest common ancestor of two nodes in a binary tree. The lowest common ancestor is the deepest node that is an ancestor of both given nodes.

**Key Pitfalls:**- It is important to handle cases where one or both of the given nodes are not present in the binary tree. - Be careful with the edge case where the given nodes are the same, as the lowest common ancestor would be the node itself. - Make sure to consider the possibility of the binary tree being empty.

Solution Summary

The best solution for finding the lowest common ancestor of a binary tree involves using a depth-first search (DFS) algorithm. Here are the steps:
1. Start from the root of the binary tree and check if it is null or equal to either of the given nodes.
2. If it is null or equal to either node, return the root.
3. Recursively search the left and right subtrees to find the lowest common ancestor.
4. If both left and right subtrees return a non-null value, it means each node is present in a different subtree, so the root is the lowest common ancestor.
5. If only one of the subtrees returns a non-null value, it means both nodes are in the same subtree, so that subtree's result is the lowest common ancestor.

Tags

Tree

Depth-First Search