DSA
Lowest Common Ancestor of a Binary Tree
10 approaches incl. Recursive, Parent Pointers + Hash Set, Path Compression (Path to Ro…, and more. Optimal — Time O(n), Space O(h).
Practice Link
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
Recursive Solution#
- Intuition: If the current node is p or q (or null), return it immediately — no need to look further. After recursing into both subtrees, if both return non-null results it means p and q are on opposite sides, so the current node is their LCA.
- Mechanics: Each call returns the first matching node found in its subtree (either p, q, their common ancestor, or null). At any node, if left returns non-null and right returns non-null, the LCA is the current node. If only one side returns non-null, that value bubbles up as the LCA candidate.
- Trade-off: This elegant post-order solution runs in O(n) time and O(h) space with no extra data structures. It does assume both p and q exist in the tree; the variation below handles the case where either might be absent.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root || root==p || root==q)
return root;
TreeNode* leftNode = lowestCommonAncestor(root->left, p,q);
TreeNode* rightNode = lowestCommonAncestor(root->right, p,q);
if(!leftNode)
return rightNode;
if(!rightNode)
return leftNode;
return root;
}
};
Time Complexity: O(n)
Space Complexity: O(n) in worst case (skewed tree), O(log n) = O(h) in best case (balanced tree)
Parent Pointers + Hash Set#
Walk the tree to build a parent map for every node. Then trace ancestors of p into a set, and walk q's ancestors until one hits the set.
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
unordered_map<TreeNode*, TreeNode*> parent;
parent[root] = nullptr;
stack<TreeNode*> stk;
stk.push(root);
// populate parent map until both p and q are found
while (parent.find(p) == parent.end() || parent.find(q) == parent.end()) {
TreeNode* node = stk.top(); stk.pop();
if (node->left) {
parent[node->left] = node;
stk.push(node->left);
}
if (node->right) {
parent[node->right] = node;
stk.push(node->right);
}
}
// collect all ancestors of p
unordered_set<TreeNode*> ancestors;
while (p) {
ancestors.insert(p);
p = parent[p];
}
// first ancestor of q that's also an ancestor of p
while (ancestors.find(q) == ancestors.end())
q = parent[q];
return q;
}
};
Time Complexity: O(n)
Space Complexity: O(n)
Path Compression (Path to Root)#
Find the full root-to-node paths for both p and q, then walk them together from the front and return the last node where they agree.
- Intuition: The root-to-node path is unique in a tree. The point at which the path to p and the path to q last share the same node is exactly the LCA — just like finding where two roads diverge from a common starting point.
- Mechanics: A DFS with backtracking fills two path vectors. Both paths are then compared element-by-element from index 0 (the root); the last equal element before the paths diverge (or one path ends) is returned as the LCA.
- Trade-off: Conceptually simple and easy to debug, but performs two full O(n) DFS traversals and stores O(h) extra path vectors. The recursive and parent-pointer approaches are strictly more space-efficient; this one is best when explicitly materialising the paths is useful for other purposes.
class Solution {
bool findPath(TreeNode* root, TreeNode* target, vector<TreeNode*>& path) {
if (!root) return false;
path.push_back(root);
if (root == target) return true;
if (findPath(root->left, target, path) || findPath(root->right, target, path))
return true;
path.pop_back();
return false;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
vector<TreeNode*> pathP, pathQ;
findPath(root, p, pathP);
findPath(root, q, pathQ);
TreeNode* lca = nullptr;
for (int i = 0; i < (int)min(pathP.size(), pathQ.size()); i++) {
if (pathP[i] == pathQ[i])
lca = pathP[i];
else
break;
}
return lca;
}
};
Time Complexity: O(n)
Space Complexity: O(n) for the two paths
Comparison#
| Recursive | Parent Pointers + Hash Set | Path Compression | |
|---|---|---|---|
| Time | O(n) | O(n) | O(n) |
| Space | O(h) stack | O(n) | O(n) |
| Style | Implicit post-order | Iterative, explicit parents | Two explicit paths |
| Early exit | Yes (returns on find) | Yes (stops once p & q found) | No (traverses full paths) |
| Best for | Clean, minimal code | When parent pointers are needed elsewhere | When full paths are useful |
Variation: p or q Might Not Exist#
The standard recursive solution returns early when it finds p or q, assuming the other must exist somewhere. If either node might be absent, we can't do that — we must fully traverse the tree and confirm both were actually found.
Key idea: track a found count alongside the LCA candidate. Only return a non-null LCA if both nodes were seen.
class Solution {
int found = 0; // counts how many of {p, q} were found
TreeNode* dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;
TreeNode* left = dfs(root->left, p, q);
TreeNode* right = dfs(root->right, p, q);
// check current node after children (post-order)
if (root == p || root == q) {
found++;
return root;
}
if (left && right) return root; // one on each side → LCA
return left ? left : right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* candidate = dfs(root, p, q);
return found == 2 ? candidate : nullptr;
}
};
Why post-order matters here: we visit children before checking root == p/q. This ensures that if p is an ancestor of q, q is counted as found (in the subtree) before we count p itself — so found correctly reaches 2 when both exist.
Time Complexity: O(n) — full traversal always
Space Complexity: O(h) recursion stack
Variation: Nodes Have Parent Pointers#
Each node has a parent field, so we can walk upward from any node to the root like a linked list.
struct Node {
int val;
Node* left;
Node* right;
Node* parent;
};
Approach 1: Hash Set of Ancestors#
Walk up from p, storing every ancestor in a set. Then walk up from q until hitting a node already in the set.
Node* lowestCommonAncestor(Node* p, Node* q) {
unordered_set<Node*> ancestors;
while (p) {
ancestors.insert(p);
p = p->parent;
}
while (ancestors.find(q) == ancestors.end())
q = q->parent;
return q;
}
Time O(h), Space O(h)
Approach 2: Two-Pointer (O(1) Space)#
Same idea as finding the intersection of two linked lists. Both pointers walk up; when one hits null it restarts from the other's original position. They meet at LCA after at most depth(p) + depth(q) steps.
Node* lowestCommonAncestor(Node* p, Node* q) {
Node* a = p;
Node* b = q;
while (a != b) {
a = a ? a->parent : q;
b = b ? b->parent : p;
}
return a;
}
Why it works: pointer a travels depth(p) steps then depth(q) steps; pointer b travels depth(q) then depth(p). Both cover the same total distance, so they meet exactly at the LCA.
Time O(h), Space O(1)
Variation: LCA of Multiple Nodes#
Find the LCA of all nodes in a given array (not just two).
Approach 1: Reduce to Pairwise LCA#
LCA is associative: LCA(a, b, c) = LCA(LCA(a, b), c). So fold over the array, accumulating the result.
class Solution {
TreeNode* lca2(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || root == p || root == q) return root;
TreeNode* left = lca2(root->left, p, q);
TreeNode* right = lca2(root->right, p, q);
if (left && right) return root;
return left ? left : right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
TreeNode* result = nodes[0];
for (int i = 1; i < nodes.size(); i++)
result = lca2(root, result, nodes[i]);
return result;
}
};
Time O(k · n), Space O(h) — k calls each costing O(n). Fine for small k, expensive otherwise.
Approach 2: Single-Pass DFS with a Set (Optimal)#
Put all target nodes in a hash set. Run one DFS — same logic as the 2-node recursive solution, but check nodeSet.count(root) instead of root == p || root == q.
Key insight: if a node in the set is an ancestor of another node in the set, returning early at the ancestor is still correct — the ancestor already "covers" its descendants for LCA purposes.
class Solution {
unordered_set<TreeNode*> nodeSet;
TreeNode* dfs(TreeNode* root) {
if (!root) return nullptr;
if (nodeSet.count(root)) return root; // covers all descendants in set too
TreeNode* left = dfs(root->left);
TreeNode* right = dfs(root->right);
if (left && right) return root;
return left ? left : right;
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
nodeSet = {nodes.begin(), nodes.end()};
return dfs(root);
}
};
Time O(n), Space O(n) for the set + O(h) stack
Follow-up: Millions of Queries on a Static Tree#
For a single query the recursive O(n) solution is fine. But if the tree never changes and you need to answer millions of LCA queries, re-running DFS each time is far too slow. The answer is to preprocess once, query cheaply.
Step 1 — Binary Lifting (O(n log n) preprocessing, O(log n) per query)#
Binary lifting is the standard stepping stone. For every node store its 2⁰, 2¹, 2², … 2^k ancestors (the k-th ancestor reachable in 2^k jumps). Then to find LCA(u, v):
- Bring u and v to the same depth by jumping up in powers of 2.
- Jump both upward in decreasing powers of 2 until they diverge — the parent of the last diverging position is the LCA.
const int LOG = 17; // 2^17 > 10^5 nodes
int up[MAXN][LOG]; // up[v][k] = 2^k-th ancestor of v
int depth[MAXN];
// Preprocess via DFS
void dfs(int v, int p, int d) {
up[v][0] = p;
depth[v] = d;
for (int k = 1; k < LOG; k++)
up[v][k] = up[up[v][k-1]][k-1]; // climb 2^k = two hops of 2^(k-1)
for (int child : adj[v])
if (child != p) dfs(child, v, d + 1);
}
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) // equalise depths
if ((diff >> k) & 1) u = up[u][k];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; k--) // lift together
if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
return up[u][0];
}
Preprocessing: O(n log n) time and space
Query: O(log n)
Step 2 — Euler Tour + Sparse Table RMQ (O(n log n) preprocessing, O(1) per query)#
To reach true O(1) per query, reduce LCA to a Range Minimum Query problem:
Euler tour: run DFS and record every node visit — including when you backtrack up through a node. A tree of n nodes produces a tour of length 2n − 1.
Tree: 1
/ \
2 3
/ \
4 5
Euler tour: 1 2 4 2 5 2 1 3 1
Depth: 0 1 2 1 2 1 0 1 0
Key observation: LCA(u, v) is the node with minimum depth in the Euler tour between the first occurrence of u and the first occurrence of v.
LCA(4, 5): first[4]=2, first[5]=4 → subarray [2 4 2 5 2] → min depth at index 1 (node 2) ✓
LCA(4, 3): first[4]=2, first[3]=7 → subarray covers node 1 (depth 0) → LCA = 1 ✓
Build a sparse table over the depth array of the Euler tour for O(1) range-minimum queries:
// After DFS fills euler[], depth[], first[]
int sparse[2*MAXN][LOG]; // sparse[i][k] = index of min-depth in [i, i+2^k)
void buildSparse(int n) {
for (int i = 0; i < n; i++) sparse[i][0] = i;
for (int k = 1; (1 << k) <= n; k++)
for (int i = 0; i + (1 << k) <= n; i++) {
int l = sparse[i][k-1], r = sparse[i + (1<<(k-1))][k-1];
sparse[i][k] = (depth[euler[l]] <= depth[euler[r]]) ? l : r;
}
}
int queryRMQ(int l, int r) { // O(1): two overlapping power-of-2 windows
int k = __lg(r - l + 1);
int a = sparse[l][k], b = sparse[r - (1<<k) + 1][k];
return (depth[euler[a]] <= depth[euler[b]]) ? euler[a] : euler[b];
}
int lca(int u, int v) {
int l = first[u], r = first[v];
if (l > r) swap(l, r);
return queryRMQ(l, r); // O(1)
}
Preprocessing: O(n log n) time and space
Query: O(1)
Comparison#
| Method | Preprocessing | Per Query | When to use |
|---|---|---|---|
| Recursive DFS | O(1) | O(n) | Single or very few queries |
| Binary Lifting | O(n log n) | O(log n) | Many queries, simpler to code |
| Euler Tour + Sparse Table | O(n log n) | O(1) | Millions of queries on a static tree |
Key insight: LCA on a static tree is secretly a Range Minimum Query in disguise. Once you see that, the standard RMQ machinery (sparse table) gives you constant-time answers for free.