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 Cracking FAANG has 67,999 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 the root of a binary tree and two nodes p and q, return their lowest common ancestor (LCA). The LCA is the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).
Approach 1: Path to Root Approach (O(n) time, O(n) space)
This approach records the path from the root to each target node. Run a DFS to build a list of nodes from the root to p, then repeat for q. Once both paths are available, iterate through them from the start and find the last common node before the paths diverge. That node is the lowest common ancestor. The tree traversal takes O(n) time in the worst case, and storing both paths requires O(n) extra space.
The method is easy to reason about because it converts the problem into comparing two arrays of ancestors. It works well when you want a clear conceptual model of ancestor relationships. The downside is the extra memory used to store both paths.
Approach 2: Recursive Depth-First Search (O(n) time, O(h) space)
This is the standard optimal solution. Traverse the tree using recursive DFS. If the current node is null, return null. If the current node matches p or q, return that node. Recursively search the left and right subtrees. If both recursive calls return non-null values, the current node is the first point where the two targets split across subtrees, making it the lowest common ancestor.
If only one side returns a node, propagate that result upward. Eventually the recursion bubbles the correct ancestor back to the root call. Each node is visited once, giving O(n) time complexity. The recursion stack consumes O(h) space where h is the tree height.
This approach works naturally with Tree recursion patterns and is commonly used in Depth-First Search problems. Since binary tree traversal is already required, the solution stays simple and avoids storing full paths.
Recommended for interviews: The recursive DFS solution is what interviewers typically expect. It demonstrates strong understanding of Binary Tree traversal and recursive reasoning. Mentioning the path-to-root approach first shows you understand the problem structure, but implementing the DFS solution proves you can optimize both memory usage and code simplicity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Path to Root Approach | O(n) | O(n) | Useful for understanding ancestor relationships or when explicit root-to-node paths are required. |
| Recursive Depth-First Search | O(n) | O(h) | Best general solution for binary trees. Minimal extra memory and standard interview approach. |