Lowest Common Ancestor
The Lowest Common Ancestor (LCA) problem seeks the shared root of the smallest subtree containing two target nodes, utilizing recursive backtracking.
What the LCA Actually Is
An ancestor of a node is any node on the path from the root down to it. The lowest common ancestor of two nodes p and q is the deepest node that is an ancestor of both — equivalently, the node where the root-to-p and root-to-q paths last coincide before diverging.
The convention that trips people up is that a node counts as its own ancestor. If q lies inside p's subtree, the answer is p itself, not p's parent. Most problem statements say so explicitly, and a solution that excludes the node from its own ancestor set fails exactly this case.
The LCA always exists in a rooted tree, because the root is an ancestor of everything — so the two paths always share at least one node. It is also unique: since ancestors of a node form a single chain from the root, the shared ancestors of p and q form a chain too, and the deepest one is well defined.
The reason it matters beyond being a puzzle is distance. In a tree the path between p and q must pass through their LCA, so dist(p, q) = depth(p) + depth(q) − 2 · depth(LCA). That formula turns a path-length query into an LCA query, which is why LCA appears underneath tree-distance problems, and why fast LCA machinery is worth building for graphs that are queried repeatedly.
An assumption worth checking before choosing a method: are p and q guaranteed to exist in the tree? The clean recursive solution below silently returns a wrong answer if one is absent, reporting the other node as the LCA. If existence is not guaranteed, either verify both are present first or track the count of matches found.
- The deepest node having both p and q in its subtree
- A node is its own ancestor — the descendant case returns p
- Always exists and is unique in a rooted tree
dist(p,q) = depth(p) + depth(q) − 2·depth(LCA)
The Recursive Method on a Binary Tree
With no ordering to exploit, the general binary tree solution is a post-order recursion of remarkable brevity, and the reason it works is worth spelling out rather than memorising.
The function returns, for the subtree at the current node, either a target node it found or null. Three cases cover it. If the node is null, return null. If the node is p or q, return that node — no need to search deeper, since a deeper match would make this node the answer anyway. Otherwise, recurse into both children.
Then examine what came back. If both sides return non-null, p was found on one side and q on the other, so the paths diverge here and this node is the LCA — return it. If only one side returns non-null, both targets lie in that subtree (or only one exists), so pass that result upward unchanged. If neither returns anything, return null.
The subtlety is in what the return value means, and it shifts. Below the LCA it means 'a target found here'; at and above the LCA it means 'the answer'. The code does not distinguish them because it does not need to — the first node where both sides come back non-null is necessarily the split point, and everything above simply relays it.
The descendant case falls out without special handling. If q is inside p's subtree, the recursion hits p first and returns immediately, never descending to find q. The parent sees one non-null side and relays p upward, which is the correct answer.
It is O(n) time — every node visited once — and O(h) space for the recursion. Since h is n on a degenerate tree, a deeply skewed input can overflow the stack; the parent-pointer alternative below avoids that.
- Return the node itself if it is p or q; otherwise recurse both ways
- Both children non-null ⇒ this node is the LCA
- One side non-null ⇒ relay it upward
- O(n) time, O(h) stack — the descendant case needs no special code
A Binary Search Tree Makes It Trivial
When the tree is a binary search tree, the ordering removes the search entirely and the problem becomes a walk down a single path.
Start at the root and compare. If both p and q are smaller than the current node, the LCA must lie in the left subtree — no path to either can bend here, since both are on the same side. If both are larger, go right. Otherwise the values split around the current node, or one equals it, and this node is the LCA.
That split condition is the whole algorithm. The first node at which p and q fall on opposite sides is precisely where their paths diverge, and by the BST invariant every node above it has both on the same side.
The result is O(h) time and, written iteratively, O(1) space — no recursion, no visiting of nodes off the path. On a balanced BST that is O(log n), against the general method's O(n). This is the difference that makes the BST version a distinct problem rather than a special case, and interviewers ask both to see whether the ordering is actually used.
Two details matter for correctness. Normalise so you do not need to know which of p and q is smaller — comparing against both bounds handles either order. And the descendant case works automatically: if p is an ancestor of q, then at p the comparison is not strictly one-sided, so p is returned.
| Method | Preprocess | Per query | Space | Needs |
|---|---|---|---|---|
| Recursive (binary tree) | None | O(n) | O(h) | Nothing |
| BST comparison | None | O(h) | O(1) iterative | BST ordering |
| Parent pointers | O(1) | O(h) | O(1) | Parent links |
| Binary lifting | O(n log n) | O(log n) | O(n log n) | Static tree |
- Both values smaller ⇒ go left; both larger ⇒ go right
- A split — or a match — means this node is the LCA
- O(h) time and O(1) space when written iteratively
- Handles the ancestor case without a special branch
Terms, operations, and practical uses
Core Concepts
- AncestorAny node on the direct path from the root to the target node, including the target node itself.
- Common AncestorA node that serves as an ancestor for both target node P and target node Q.
- Lowest Common AncestorThe deepest possible common ancestor; the exact point where the paths to P and Q diverge.
Standard Binary Tree
- Post-order ApproachRecursively search left and right. If both return a non-null target, the current node is the LCA.
- Single Target ReturnIf only one side finds a target, pass that target up to the parent. It assumes both P and Q exist in the tree.
- Path RecordingAn alternative O(N) space method is to record the path from root to P and root to Q, then find the last matching node.
Optimizations
- BST LCAIn a BST, traverse down from root; the first node with a value strictly between P and Q is definitively the LCA.
- Parent PointersIf nodes have parent references, track the path from P to root using a hash set, then traverse up from Q until a match is found.
- Binary LiftingPrecomputing a jump table in O(N log N) to answer millions of LCA queries on a static tree in O(log N) time per query.
Find the lowest common ancestor
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def lca(root, p, q):
if not root or root == p or root == q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right:
return root
return left if left else right
six, two = TreeNode(6), TreeNode(2)
five = TreeNode(5, six, two)
root = TreeNode(3, five, TreeNode(1, TreeNode(0), TreeNode(8)))
print('LCA(6, 2) =', lca(root, six, two).val)#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x, TreeNode* l = nullptr, TreeNode* r = nullptr) : val(x), left(l), right(r) {
}
};
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lca(root->left, p, q);
TreeNode* right = lca(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
int main() {
TreeNode* six = new TreeNode(6);
TreeNode* two = new TreeNode(2);
TreeNode* five = new TreeNode(5, six, two);
TreeNode* root = new TreeNode(3, five, new TreeNode(1, new TreeNode(0), new TreeNode(8)));
cout << "LCA(6, 2) = " << lca(root, six, two)->val << '\n';
}public class Main {
static class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) {
val = x;
}
TreeNode(int x, TreeNode l, TreeNode r) {
val = x;
left = l;
right = r;
}
}
static TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lca(root.left, p, q);
TreeNode right = lca(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
public static void main(String[] args) {
TreeNode six = new TreeNode(6), two = new TreeNode(2);
TreeNode five = new TreeNode(5, six, two);
TreeNode root = new TreeNode(3, five, new TreeNode(1, new TreeNode(0), new TreeNode(8)));
System.out.println("LCA(6, 2) = " + lca(root, six, two).val);
}
}Step through it
Running on tree rooted at 3, find LCA of 6 and 2
Read all 11 Steps
- Find LCA(6, 2) Both targets live in the left subtree. The search returns evidence upward rather than searching downward twice.
- Visit root 3 3 is neither target, so recurse into both children and see what each reports back.
- Go left to 5 Recurse into 5. Its subtree contains both 6 and 2, though we do not know that yet.
- Go left to 6 Recurse into 6 — this is one of the targets.
- 6 is a target A node that matches a target returns itself immediately. No need to search below it.
- Go right to 2 Now the right child of 5. This is the other target.
- 2 is a target 2 returns itself up to 5.
- 5 sees both sides Node 5 got a non-null answer from its left AND its right. Both targets are below it and on different sides — so 5 itself is the LCA.
- Right subtree of 3 For completeness, 3's right child 1 is searched and finds neither target, returning null.
- One side only 3 heard from its left but not its right, so it passes the left answer straight up unchanged.
- Answer LCA(6, 2) = 5. One post-order pass, O(n) time, and the split point is found the moment a node hears from both sides.
Binary Lifting for Repeated Queries
The methods above cost O(n) or O(h) per query. When thousands of queries hit the same static tree, preprocessing pays for itself, and binary lifting is the standard approach.
The idea is to precompute, for every node, its ancestor 2^k levels up for each power of two — a table up[k][v]. The recurrence builds it cheaply: the 2^k-th ancestor is the 2^(k−1)-th ancestor of the 2^(k−1)-th ancestor, so up[k][v] = up[k−1][ up[k−1][v] ]. With a depth array from one DFS, building the whole table costs O(n log n) time and space.
A query then runs in two stages. First, level the two nodes: if p is deeper than q, lift p by the powers of two summing to the depth difference — the binary representation of that difference says exactly which jumps to take. Second, if they are now the same node, that is the answer.
Otherwise lift both together, from the largest power downward, jumping only when the two ancestors at that height differ. Jumping only on a difference keeps both nodes strictly below the LCA throughout; when the loop finishes they sit on its two children, so the answer is up[0][p] — the parent.
That last step is the counterintuitive part and the usual source of bugs: the loop deliberately never lands on the LCA, because equality at some height does not prove that height is the lowest such node. Stopping just below and taking one parent step is what guarantees the lowest ancestor.
Each query is O(log n). The alternative worth knowing is reducing LCA to a range minimum query over an Euler tour, which with a sparse table answers queries in O(1) after O(n log n) preprocessing — better asymptotically, though binary lifting is more commonly implemented because the same up table also answers 'find the kth ancestor' directly.
up[k][v] = up[k−1][up[k−1][v]], built in O(n log n)- Level the deeper node first using the binary digits of the depth gap
- Then lift both together, jumping only where the ancestors differ
- Stop below the LCA and take one parent step — O(log n) per query