Lowest Common Ancestor of a Binary Tree
Medium· DFS· LCA
Problem
Given a binary tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as its own descendant.
Examples
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Node 4 lies under node 5, so 5 is its own LCA with 4.
Constraints
- • 2 <= number of nodes <= 10^5
- • All values are unique
- • p and q both exist in the tree and p != q
Hints & approach
Hint 1
Ask each subtree: did you find p or q?
Hint 2
If the left subtree reports one target and the right subtree reports the other, the current node is the split point.
Hint 3
If the current node is p or q itself, you can return it immediately.
Approachtry the hints first
Recurse: if the node is null, p, or q, return it. Otherwise recurse into both children. If both calls return non-null, p and q are on different sides, so the current node is the LCA. If only one is non-null, pass that result up. The first node where the two sides meet is the answer.
Time O(n) · Space O(h)