Lowest Common Ancestor (LCA) in Binary Trees
Quick Overview
If the two targets sit in different subtrees, the current node is their meeting point. That single observation solves LCA in one post-order `O(N)` pass with no parent pointers.
Deep Dive
1. Defining Common Ancestors
The Lowest Common Ancestor (LCA) of two nodes p and q in a tree is the deepest node that has both p and q as descendants (where a node can be a descendant of itself).
3 (LCA of 5 and 1)
/ \
[5] [1]
/ \ / \
6 2 0 8
/ \
7 4
2. Divide and Conquer Recursive Approach
For any subtree rooted at root:
- If
rootisnull,p, orq, returnroot. - Recursively search the left subtree and right subtree.
- If both left and right return non-null,
rootis the split point and therefore the LCA! - If only one side returns non-null, pass that non-null node up.
function lowestCommonAncestor(root, p, q) {
// Base case: Reached null or found p or q
if (!root || root === p || root === q) {
return root;
}
const left = lowestCommonAncestor(root.left, p, q);
const right = lowestCommonAncestor(root.right, p, q);
// If p and q are found in different subtrees, root is the LCA!
if (left !== null && right !== null) {
return root;
}
// Otherwise, return whichever subtree found a target
return left !== null ? left : right;
}
3. Optimized LCA on a Binary Search Tree (BST)
On a BST, we can use the ordering invariant to find LCA in O(H) time without full tree exploration:
function lowestCommonAncestorBST(root, p, q) {
while (root) {
if (p.val < root.val && q.val < root.val) {
root = root.left; // Both targets in left subtree
} else if (p.val > root.val && q.val > root.val) {
root = root.right; // Both targets in right subtree
} else {
return root; // Split point found!
}
}
return null;
}
4. Common Mistakes
- Assuming Binary Tree is a BST: Applying the BST comparison optimization on an unsorted generic binary tree fails. Use the general divide-and-conquer approach for generic binary trees.
5. Next Steps
Use divide-and-conquer on tree subproblems. Next, let's explore Heaps and Priority Queues!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.