Lowest Common Ancestor of a Binary Tree
MediumThe first node with a hit on both sides
Problem
Return the lowest common ancestor of two nodes in a binary tree.
Recurse; the node where the two targets first appear in different subtrees is their lowest common ancestor.
The idea
Search both subtrees for either target and return whichever node you find. When a node gets a non-null result from both sides, the two targets are on opposite sides and that node is the ancestor.
The trick
- The LCA is the deepest node where the two targets first fall into different subtrees.
- A node is also the answer if it is itself one target and the other lies somewhere below it.
Step 1 of 5. Find the lowest common ancestor of 4 and 5. Recurse; a node that sees both targets below it is the answer.
Split point of both paths.
1function lca(node, p, q) {2 if (!node || node === p || node === q) return node;3 const l = lca(node.left, p, q);4 const r = lca(node.right, p, q);5 return l && r ? node : (l ?? r);6}Input
- nodes
- 6, 5 edges
Memory
- left
- —
- right
- —
Output
- LCA
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [3,5,1,6,2,0,8], p = 5, q = 1
- Output:
- 3
- Explanation:
- 5 and 1 meet at the root 3.
Example 2
- Input:
- tree = [3,5,1,6,2,0,8], p = 6, q = 2
- Output:
- 5
- Explanation:
- 6 and 2 both sit under 5.
Example 3
- Input:
- tree = [1,2], p = 1, q = 2
- Output:
- 1
- Explanation:
- The root is their meeting point.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.