Lowest Common Ancestor of a Binary Tree
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
