MediumNeetCode150TreeDepth-First SearchBinary Tree
Lowest Common Ancestor of a Binary Tree
Find the LCA of two nodes.
Examples
Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
LCA of 5 and 1 is 3.
Constraints
- •
Number of nodes in [2,10^5] - •
-10^9 <= Node.val <= 10^9 - •
All values unique, p != q
Approaches
Find paths and compare.
CodeT: O(n) | S: O(n)
Return node if found.
CodeT: O(n) | S: O(h)
def lowestCommonAncestor(root, p, q):
if not root or root==p or root==q: return root
l=lowestCommonAncestor(root.left,p,q)
r=lowestCommonAncestor(root.right,p,q)
if l and r: return root
return l if l else rSame approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Store Path | O(n) | O(n) | Find paths and compare. |
| DFS Recursive | O(n) | O(h) | Return node if found. |
| DFS Recursive Optimized | O(n) | O(h) | Same approach. |
Store Path
T: O(n)S: O(n)
Find paths and compare.
DFS Recursive
T: O(n)S: O(h)
Return node if found.
DFS Recursive Optimized
T: O(n)S: O(h)
Same approach.
Common Mistakes
Not handling ancestor case
Returning value not node
Forgetting p,q guaranteed