Lowest Common Ancestor
A favorite interview problem: find the deepest node that is an ancestor of two others, in a plain binary tree and in a BST.
On this page
The lowest common ancestor (LCA) of two nodes is the deepest node that has both of them as descendants - the point where the paths to the two nodes diverge. It's one of the most-asked tree problems because its clean recursive solution is a perfect test of tree thinking.
LCA in a plain binary tree
The recursive insight: the LCA is the node where one target is found in its left subtree and the other in its right subtree (or the node is one of the targets). Search returns each target up the tree, and the node that first "sees" both from different sides is the answer:
// LCA in a binary tree — O(n)
TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
if (node == null || node == p || node == q) return node; // found a target (or hit null)
TreeNode left = lca(node.left, p, q);
TreeNode right = lca(node.right, p, q);
if (left != null && right != null) return node; // targets split here → this is the LCA
return left != null ? left : right; // both on one side → pass it up
}Read the combine step carefully: if the left recursion found something and the right recursion found something, the two targets are in different subtrees, so this node is where they meet - the LCA. If only one side found a target, the LCA is somewhere up that side, so pass it upward. It's a single postorder pass, O(n).
LCA in a BST is even simpler
If the tree is a BST, you don't need to search both subtrees - the ordering tells you which way to go. Walk down from the root: if both targets are smaller, go left; if both larger, go right; the moment they split (one smaller, one larger, or you hit one of them), you're at the LCA:
// LCA in a BST — O(h), no full search needed
TreeNode lcaBST(TreeNode node, TreeNode p, TreeNode q) {
while (node != null) {
if (p.val < node.val && q.val < node.val) node = node.left;
else if (p.val > node.val && q.val > node.val) node = node.right;
else return node; // split point (or a target) → LCA
}
return null;
}The BST version is O(h) - O(log n) in a balanced tree - because it never explores subtrees that can't contain the answer.
The 'split point' is the pattern
LCA is really about finding where two downward paths diverge. In a BST that's the node where the target values straddle it; in a general tree it's the node whose two subtrees each contain one target. Many tree problems ('distance between two nodes,' 'path between two nodes') build on finding the LCA first.
Given two people in a family tree, their lowest common ancestor is the most recent relative they both descend from - trace each person's line upward and it's where the two lines first merge. You don't need the founder of the family (a common ancestor, but not the lowest); you want the nearest shared one. In a BST, birth order lets you shortcut: if both people sort 'earlier' than the current ancestor, their merge point is further down the earlier branch - so you walk straight to the divergence instead of searching the whole tree.
For the general binary-tree algorithm, explain what the function returns in three cases: (a) the current node is one of the two targets; (b) both targets are found in different subtrees of the current node; (c) both targets are in the same subtree. Why do these three cases cover everything?
In a binary tree, when is the current node the lowest common ancestor of p and q?
Key takeaways
- The lowest common ancestor is the deepest node having both targets as descendants - where their paths diverge.
- In a binary tree, LCA is found by postorder recursion: the node whose left and right subtrees each contain one target is the LCA (O(n)).
- A node can be its own ancestor: if the current node is a target, return it.
- In a BST, walk down comparing values - the split point (targets straddle the node) is the LCA, in O(h).
- LCA is a building block for path-between-nodes and distance-between-nodes problems.