Lowest common ancestor
Scenario
Two branches in Git split from a common commit 50 commits ago. To merge them, Git needs to find the exact point where their paths diverged.
How do you find the lowest node in a tree that has two target nodes as descendants?
Why it exists
Problem: Finding the shared origin of two nodes by traversing parent pointers requires extra memory or parent pointers that standard binary trees do not store.
Naive approach: Storing root-to-node paths for both nodes in lists, then scanning the lists to find the last common node (uses extra O(n) space).
Better idea: Use top-down BST splitting logic for BSTs (O(1) extra space), or post-order bottom-up recursion for general binary trees to identify the exact node where p and q diverge.
Mental model
Find the split point: the lowest node where target p and target q branch off in different directions.
For BSTs: start at root; if both p and q are smaller than node.val, move left; if both are larger, move right; as soon as p and q split (or one equals node.val), node is the LCA. For general trees: post-order recurse; if a node finds p or q in its left subtree AND right subtree, that node is the LCA.
Repeated decision: are p and q both on the same side of this node, or does this node split them?
Explanation
The Lowest Common Ancestor (LCA) of two nodes `p` and `q` is defined as the deepest node in the tree that has both `p` and `q` as descendants (where a node is allowed to be a descendant of itself).
Case 1: LCA in a Binary Search Tree (O(h) time, O(1) space)
Because a BST is ordered:
1. If `p.val < node.val` and `q.val < node.val`, both targets lie in the left subtree -> move `node = node.left`.
2. If `p.val > node.val` and `q.val > node.val`, both targets lie in the right subtree -> move `node = node.right`.
3. Otherwise, `p` and `q` split (or one equals `node.val`). `node` IS the LCA!
Case 2: LCA in a General Binary Tree (O(n) time, O(h) space)
When no search ordering exists, use bottom-up post-order recursion:
`def lca(node, p, q)`:
- `if not node or node == p or node == q: return node`
- `left = lca(node.left, p, q)`
- `right = lca(node.right, p, q)`
- `if left and right: return node` (Both subtrees found a target -> `node` is LCA!)
- `return left if left else right` (Pass found target upwards)
Walkthrough on General Tree:
Tree:
3
/ \
5 1
/ \
6 2
LCA of 6 and 2:
- Call on root `3`: recurse left to `5` and right to `1`.
- At `5`: recurse left to `6` (matches `p`, returns `6`) and right to `2` (matches `q`, returns `2`).
- At `5`: `left` is `6` and `right` is `2`. Both non-null -> `5` returns itself as LCA!
- At `3`: `left` returns `5`, `right` returns `None`. Return `5` as final answer.
Key points
- Self-Ancestry: A node can be its own descendant. If p is an ancestor of q, LCA(p, q) = p.
- BST Split Point: In a BST, LCA is the first node where p and q are no longer on the same side.
- General Tree Post-Order Convergence: In a general tree, LCA is the first node where left and right recursive calls both return non-null nodes.
Pattern: Lowest Common Ancestor (LCA)
Recognition cues:
- two target nodes in a tree
- shared ancestor search
- BST split point or post-order match
Failure signals
- Problem asks for the common origin or lowest ancestor of two elements in a tree structure.
- Finding `git merge-base` between two branch commits.
Engineering examples
Git Merge-Base Calculation (`git merge-base`)
Find the common ancestor commit of two branches to compute a 3-way git merge diff.
Commits in Git form a Directed Acyclic Graph (DAG) tree structure where `git merge-base` calculates the LCA of two commit hashes.
UI Event Bubbling / Common Container
Find the lowest DOM element container encompassing two clicked UI components.
DOM tree LCA finds the nearest enclosing parent element to apply event handling or focus scope.
When not to use
- Graphs with cycles or multiple paths without tree properties: General LCA algorithms assume a single unique root path tree DAG structure.
Common mistakes
- Assuming LCA cannot be p or q itself: If node p is an ancestor of node q, then LCA(p, q) is p itself. Assuming LCA must be a parent above both p and q causes incorrect null returns.
- Applying BST split logic to a non-BST binary tree: Comparing node values to p and q relies on BST sortedness. Applying this to a general tree yields invalid search directions.
- Assuming parent pointers exist: Standard binary tree nodes only store `left` and `right` child pointers, requiring top-down or bottom-up traversal.
Recall questions
- What is the definition of Lowest Common Ancestor (LCA) of nodes p and q?
- How do you find the LCA of two nodes in a Binary Search Tree (BST)?
- In general binary tree LCA recursion, how do you know when a node is the LCA?
Questions & answers
Lowest Common Ancestor of a Binary Search Tree: Given a BST and nodes p and q, find their LCA.
Start at root. Iteratively move to left child if both p,q < root.val, or right child if both p,q > root.val. Return current node when they split.
Approach: Iterative BST search split point in O(h) time, O(1) space.
Lowest Common Ancestor of a Binary Tree: Given a general binary tree and nodes p and q, find their LCA.
Use bottom-up DFS recursion. If node is None, p, or q, return node. Recurse left and right. If both return non-null, current node is LCA.
Approach: Post-order bottom-up DFS tracking subtree target matches.
Interesting facts
- In competitive programming, LCA queries on static trees can be answered in O(1) time after O(n log n) precomputation using binary lifting or Euler tour + RMQ!
Continue learning
Previous: Binary tree & traversals
Previous: BST: insert & search
Next: Height & diameter
Related: Binary tree & traversals
Related: BST: insert & search
Related: Validate a BST