Watch 10 video solutions for Lowest Common Ancestor of a Binary Tree, a medium level problem involving Tree, Depth-First Search, Binary Tree. This walkthrough by take U forward has 379,697 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Example 3:
Input: root = [1,2], p = 1, q = 2 Output: 1
Constraints:
[2, 105].-109 <= Node.val <= 109Node.val are unique.p != qp and q will exist in the tree.Problem Overview: Given a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the deepest node that has both nodes as descendants, where a node can be a descendant of itself.
Approach 1: Recursive Depth-First Search (O(n) time, O(h) space)
This approach performs a post-order traversal using recursion. Traverse the tree with DFS and return the current node when it matches either p or q. Each recursive call checks the left and right subtree results: if both sides return a non-null node, the current node is the lowest common ancestor. If only one side returns a node, propagate that node upward. The algorithm touches each node once, giving O(n) time complexity, while recursion stack depth is bounded by the tree height O(h). This approach works naturally with tree recursion and is the most common interview solution.
Approach 2: Path to Root Approach (O(n) time, O(n) space)
This method explicitly stores the path from the root to each target node. Run a DFS to build two arrays: one for the path from root to p, and another for root to q. After both paths are built, iterate through them until the nodes diverge; the last common node is the LCA. Each DFS traversal may visit the entire tree, leading to O(n) time. Storing paths requires O(n) space in the worst case. This approach is easier to reason about when learning depth-first search but uses more memory than the recursive solution.
Recommended for interviews: The recursive DFS solution is what most interviewers expect. It demonstrates strong understanding of binary tree traversal and recursive problem decomposition. The path-based approach shows clear reasoning about ancestor relationships, but the recursive method is cleaner and more space-efficient.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search | O(n) | O(h) | General case and most interview scenarios; clean recursive logic |
| Path to Root Approach | O(n) | O(n) | Useful for learning LCA intuition or when explicit root-to-node paths are needed |