#236
Lowest Common Ancestor of a Binary Tree
Medium Postorder search
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given two nodes p and q in a binary tree, return their lowest common ancestor (a node may be an ancestor of itself).
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the deepest node that has both p and q below it (or is one of them).
Why this works: search both sides. If p is found on one side and q on the other, this node is where they split.
Example: p = 5, q = 1 in a tree rooted at 3 with children 5 and 1
left finds 5, right finds 1 → answer 3✦Hints open one at a time
Search both subtrees for p or q.
If both sides return something, the current node is the split point — the LCA.
↗Approach
lca(node): if null or equal to p or q, return node. Recurse left and right. If both non-null, return node; otherwise return whichever is non-null.
</>Solution (Java)
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root; // p and q on different sides
return left != null ? left : right;
}
}!Common mistake
Storing full root-to-node paths in lists — works, but uses more memory and code.
Complexity
- Time: O(n).
- Space: O(h).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon