Lowest Common Ancestor
The Intuition
Picture a family tree hanging on your wall. Two cousins point at it and ask, "Who's our closest shared ancestor?" You could trace a finger from each cousin upward toward the root, marking every person along the way. The first name that both paths touch is your answer. That's the Lowest Common Ancestor.
Now imagine you're standing at the root of the tree, looking down. You ask, "Where is cousin A?" Someone on the left side raises their hand. "Where is cousin B?" Someone on the right side raises their hand. If the two cousins are on opposite sides of you, then you are their closest shared ancestor. There's no one deeper in the tree who could claim both of them.
But what if both cousins are on the same side? Then you're not the answer. The real LCA is deeper, somewhere in that subtree where both of them live. So you walk down to that side and ask the same question again. Left or right? Same side or different sides? You keep narrowing until you find the split point.
In a binary search tree, you get an extra shortcut. You don't need to search blindly. If both cousins have values smaller than yours, go left. Both larger, go right. The moment one is smaller and one is larger (or one of them is you), you've found your spot. The BST property turns the search into a straight walk down the tree.
Finding the LCA of two nodes in a binary tree or BST, distance between two nodes, path queries in trees, or any problem requiring the meeting point of two upward paths.
- Need distance between nodes (use BFS)
- Graph is not a tree (use different ancestor algorithm)
- Need LCA of more than 2 nodes simultaneously (extend with different approach)
Variations:
- General binary tree: Recursive DFS checking both subtrees.
- BST variant: Use value comparisons to navigate. O(h) time, O(1) space.
- With parent pointers: Treat as a linked list intersection problem.
- Binary lifting: Pre-process O(n log n) for O(log n) per LCA query -- ideal for multiple queries.
- one node is the ancestor of the other
- both queries target the same node
- root is the answer
Key Points
- •LCA is the deepest node that is an ancestor of both target nodes
- •Recursive approach: if current node is p or q, return it
- •If left and right subtrees both return non-null, current node is the LCA
- •For BST: use value comparisons to go left or right
- •Binary lifting pre-processes for O(log n) per query with multiple queries
Code Template
1 def lowest_common_ancestor(root, p, q):
2 """LCA of two nodes in a binary tree."""
3 if not root or root == p or root == q:
4 return root
5
6 left = lowest_common_ancestor(root.left, p, q)
7 right = lowest_common_ancestor(root.right, p, q)
8
9 if left and right:
10 return root # p and q are in different subtrees
11 return left if left else right
12
13 def lca_bst(root, p, q):
14 """LCA in a Binary Search Tree (use values)."""
15 while root:
16 if p.val < root.val and q.val < root.val:
17 root = root.left
18 elif p.val > root.val and q.val > root.val:
19 root = root.right
20 else:
21 return root
22 return None
23
24 def lca_with_parent(p, q):
25 """LCA when nodes have parent pointers (like linked list intersection)."""
26 a, b = p, q
27 while a != b:
28 a = a.parent if a else q
29 b = b.parent if b else p
30 return aCommon Mistakes
- Not handling the case where one node is an ancestor of the other
- Confusing the BST variant (compare values) with the general variant (check identity)
- Forgetting that both p and q are guaranteed to exist in the tree