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.
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
For any subtree rooted at root:
root is null, p, or q, return root.root is the split point and therefore the LCA!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;
}
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;
}
Use divide-and-conquer on tree subproblems. Next, let's explore Heaps and Priority Queues!
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.
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.
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.