Introduction to Lowest Common Ancestor
The Lowest Common Ancestor (LCA) is one of those classic tree problems that shows up everywhere — from interview rooms at big tech companies to real-world systems like version control, network routing, and bioinformatics. At its core, the LCA of two nodes in a tree is the deepest node that has both nodes as descendants (where a node can be considered a descendant of itself).
In this tutorial, we'll walk through what the LCA is, why it matters, and how to implement it efficiently in Python. We'll start with the intuitive recursive approach, then move on to more advanced techniques like binary lifting that handle repeated queries on large trees.
What Is the Lowest Common Ancestor?
Imagine a family tree. The lowest common ancestor of two people is the most recent grandparent they share. In computer science terms, given a rooted tree and two nodes u and v, the LCA is the deepest node w such that both u and v are descendants of w.
Consider this binary tree:
3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
For nodes 7 and 4, the LCA is 2. For nodes 5 and 1, the LCA is 3. And for nodes 5 and 4, the LCA is 5 itself, because a node is its own ancestor.
Why the LCA Matters
The LCA isn't just an academic exercise. It has concrete applications across many domains:
- Version control systems: Git uses LCA-like logic to find the merge base of two branches — the common commit from which both branches diverged.
- Computational biology: Phylogenetic trees use LCA to find the most recent common ancestor of two species, which is fundamental to evolutionary analysis.
- Network routing: In hierarchical network topologies, the LCA helps determine the meeting point of two paths.
- Range queries on trees: Many tree problems reduce to LCA, including distance queries between two nodes (distance = depth[u] + depth[v] - 2*depth[LCA]).
- Compiler design: Type hierarchies and class inheritance trees use LCA to find common supertypes.
Understanding how to compute the LCA efficiently is therefore a foundational skill for any developer working with hierarchical data.
Setting Up the Tree Structure
Before we can compute the LCA, we need a tree representation. For most LCA problems, a simple node class works well. Here's a basic binary tree node:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def __repr__(self):
return f"TreeNode({self.val})"
# Build the example tree from above
def build_example_tree():
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
root.right.left = TreeNode(0)
root.right.right = TreeNode(8)
root.left.right.left = TreeNode(7)
root.left.right.right = TreeNode(4)
return root
For more general trees (not necessarily binary), you'd store a list of children instead of explicit left and right pointers. The LCA algorithms we'll discuss work for both, but the binary case is the most common starting point.
Approach 1: Recursive Depth-First Search
The most intuitive approach uses recursion. The idea is elegant: traverse the tree from the root. If the current node is one of the target nodes, return it. Otherwise, recurse into both children. If both recursive calls return a non-null result, the current node is the LCA. If only one side returns a non-null result, propagate that result upward.
Implementation
def lowest_common_ancestor(root, p, q):
"""
Recursive DFS approach.
Time: O(n) — visits each node once
Space: O(h) — recursion stack, h = tree height
"""
# Base case: empty subtree or found one of the targets
if root is None or root is p or root is q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found a target, current node is the LCA
if left and right:
return root
# Otherwise, propagate the non-null result upward
return left if left else right
# Example usage
root = build_example_tree()
node5 = root.left # Node 5
node1 = root.right # Node 1
node7 = root.left.right.left # Node 7
node4 = root.left.right.right # Node 4
print(lowest_common_ancestor(root, node7, node4)) # TreeNode(2)
print(lowest_common_ancestor(root, node5, node1)) # TreeNode(3)
print(lowest_common_ancestor(root, node5, node4)) # TreeNode(5)
How It Works
The recursion works bottom-up. Each call returns one of three things:
None— neitherpnorvwas found in this subtree.- The node itself — if the current node matches
porq, we stop searching deeper and return immediately. - The LCA — when both children return non-null, the current node is the meeting point.
This approach assumes both p and q actually exist in the tree. If that's not guaranteed, you'll need a separate pass to verify their existence first.
Approach 2: Storing Parent Pointers
If you can modify the tree to store parent pointers, there's an alternative approach that mirrors the "intersection of two linked lists" problem. You collect the path from each node up to the root, then find the first common node.
def lowest_common_ancestor_with_parents(p, q):
"""
Uses parent pointers to find LCA.
Time: O(h)
Space: O(h)
"""
# Collect ancestors of p
ancestors = set()
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk q upward; first ancestor in the set is the LCA
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None # No common ancestor (shouldn't happen in a valid tree)
class TreeNodeWithParent:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
self.parent = None
def __repr__(self):
return f"TreeNodeWithParent({self.val})"
This is particularly useful when the tree is immutable and you can't recurse freely, or when you already have parent pointers for other reasons (like in many DOM implementations).
Approach 3: Binary Lifting for Repeated Queries
The recursive approach is fine for a single query, but what if you need to answer thousands of LCA queries on the same large tree? Recomputing from scratch each time is wasteful. Binary lifting precomputes information that lets you answer each query in O(log n) time after O(n log n) preprocessing.
The core idea: for each node, precompute its 2^k-th ancestor for all valid k. To find the LCA, first bring both nodes to the same depth using these jumps, then jump both upward in powers of two until they meet.
Implementation
import math
from collections import deque
class BinaryLiftingLCA:
def __init__(self, n, adj, root=0):
"""
n: number of nodes (labeled 0..n-1)
adj: adjacency list (undirected tree)
root: root node index
"""
self.n = n
self.LOG = max(1, math.floor(math.log2(n)) + 1)
self.depth = [0] * n
self.parent = [[-1] * n for _ in range(self.LOG)]
self._bfs(adj, root)
self._build_sparse_table()
def _bfs(self, adj, root):
visited = [False] * self.n
queue = deque([root])
visited[root] = True
self.depth[root] = 0
self.parent[0][root] = -1
while queue:
u = queue.popleft()
for v in adj[u]:
if not visited[v]:
visited[v] = True
self.depth[v] = self.depth[u] + 1
self.parent[0][v] = u
queue.append(v)
def _build_sparse_table(self):
for k in range(1, self.LOG):
for v in range(self.n):
if self.parent[k - 1][v] != -1:
self.parent[k][v] = self.parent[k - 1][self.parent[k - 1][v]]
def query(self, u, v):
"""Return LCA of nodes u and v in O(log n)."""
# Ensure u is the deeper node
if self.depth[u] < self.depth[v]:
u, v = v, u
diff = self.depth[u] - self.depth[v]
# Lift u up to the same depth as v
for k in range(self.LOG):
if diff & (1 << k):
u = self.parent[k][u]
if u == v:
return u
# Lift both up together
for k in range(self.LOG - 1, -1, -1):
if self.parent[k][u] != self.parent[k][v]:
u = self.parent[k][u]
v = self.parent[k][v]
return self.parent[0][u]
# Example: a tree with 9 nodes
# 0
# /|\
# 1 2 3
# | |
# 4 5
# / \
# 6 7
# |
# 8
n = 9
adj = [[] for _ in range(n)]
edges = [(0,1),(0,2),(0,3),(1,4),(3,5),(5,6),(5,7),(7,8)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
lca = BinaryLiftingLCA(n, adj, root=0)
print(lca.query(4, 8)) # 0
print(lca.query(6, 8)) # 5
print(lca.query(4, 1)) # 1
Why Binary Lifting Is Powerful
With O(n log n) preprocessing, you get O(log n) per query. For a tree with a million nodes and a million queries, that's the difference between O(n^2) and O(n log n) total work — a massive speedup. This is the standard approach in competitive programming and in production systems that need to answer many LCA queries.
Approach 4: Euler Tour with RMQ
There's an even more advanced technique that reduces LCA to a Range Minimum Query (RMQ) problem. You perform an Euler tour of the tree (recording nodes as you visit them, including on the way back up), and then the LCA of two nodes is the node with minimum depth in the range between their first appearances in the tour.
With a sparse table for RMQ, this gives O(n log n) preprocessing and O(1) per query — the asymptotically optimal approach. However, the constant factors and implementation complexity make binary lifting the more practical choice in most real-world scenarios.
Computing Distance Between Nodes
One of the most common applications of LCA is computing the distance between two nodes in a tree. The formula is simple:
def distance(adj, n, u, v, root=0):
"""
Distance between u and v in a tree.
Uses binary lifting under the hood.
"""
lca_solver = BinaryLiftingLCA(n, adj, root)
w = lca_solver.query(u, v)
return lca_solver.depth[u] + lca_solver.depth[v] - 2 * lca_solver.depth[w]
# Using the same tree from before
print(distance(adj, n, 4, 8)) # 5 (4->1->0->3->5->7->8 is 6 edges... let's verify)
# Path: 4-1-0-3-5-7-8 = 6 edges
# depth[4]=2, depth[8]=4, LCA=0 (depth 0)
# 2 + 4 - 0 = 6 ✓
This works because the path from u to v always passes through their LCA. You go up from u to the LCA, then down to v.
Best Practices
Choose the Right Approach for Your Use Case
Don't reach for binary lifting if you only need a single LCA computation on a small tree. The recursive approach is simpler, more readable, and perfectly adequate. Reserve the advanced techniques for when you have many queries or very large trees.
Validate Your Inputs
The recursive approach assumes both nodes exist in the tree. If there's any chance they don't, add a verification step:
def find_node(root, target):
if root is None:
return False
if root is target:
return True
return find_node(root.left, target) or find_node(root.right, target)
def safe_lca(root, p, q):
if not find_node(root, p) or not find_node(root, q):
raise ValueError("One or both nodes not found in tree")
return lowest_common_ancestor(root, p, q)
Watch Out for Recursion Limits
Python's default recursion limit is 1000. For deep trees, the recursive approach will hit this limit. Either increase it with sys.setrecursionlimit() or convert the recursion to an iterative approach using an explicit stack.
import sys
sys.setrecursionlimit(10**6)
Handle Edge Cases Explicitly
Always consider these edge cases in your tests:
- One node is the ancestor of the other (LCA should be the ancestor node itself).
- Both nodes are the same (LCA is that node).
- One node is the root (LCA is the root if the other node is in the tree).
- The tree is a single node.
- The tree is a linear chain (degenerate case).
Use Iterative Approaches for Production
For production code dealing with untrusted input, prefer iterative implementations. They avoid stack overflow risks and are often easier to debug. Here's an iterative version of the recursive approach using path tracking:
def lowest_common_ancestor_iterative(root, p, q):
"""
Iterative approach using path tracking.
Time: O(n)
Space: O(h)
"""
def find_path(node, target, path):
if node is None:
return False
path.append(node)
if node is target:
return True
if (find_path(node.left, target, path) or
find_path(node.right, target, path)):
return True
path.pop()
return False
path_p, path_q = [], []
find_path(root, p, path_p)
find_path(root, q, path_q)
lca = None
for a, b in zip(path_p, path_q):
if a is b:
lca = a
else:
break
return lca
Testing Your Implementation
Always write tests covering the edge cases mentioned above. Here's a quick test suite:
def test_lca():
root = build_example_tree()
n = lambda v: None # placeholder
# Map values to nodes for clarity
nodes = {}
def index(node):
nodes[node.val] = node
from collections import deque
queue = deque([root])
while queue:
node = queue.popleft()
index(node)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
# Test 1: LCA of 7 and 4 is 2
assert lowest_common_ancestor(root, nodes[7], nodes[4]).val == 2
# Test 2: LCA of 5 and 1 is 3
assert lowest_common_ancestor(root, nodes[5], nodes[1]).val == 3
# Test 3: LCA of 5 and 4 is 5 (one is ancestor of other)
assert lowest_common_ancestor(root, nodes[5], nodes[4]).val == 5
# Test 4: LCA of 6 and 4 is 5
assert lowest_common_ancestor(root, nodes[6], nodes[4]).val == 5
# Test 5: LCA of 0 and 8 is 1
assert lowest_common_ancestor(root, nodes[0], nodes[8]).val == 1
# Test 6: Same node
assert lowest_common_ancestor(root, nodes[2], nodes[2]).val == 2
print("All tests passed!")
test_lca()
Conclusion
The Lowest Common Ancestor is a deceptively simple problem with surprisingly deep applications. For most everyday use cases — a single query on a moderately sized tree — the recursive DFS approach is clean, readable, and efficient enough. When you need to handle many queries on large trees, binary lifting provides an excellent balance of implementation simplicity and query performance. And for the truly performance-critical scenarios, the Euler tour plus RMQ approach gives you constant-time queries after linearithmic preprocessing. The key is understanding the tradeoffs: start simple, profile your actual workload, and only reach for the more complex techniques when the data demands it. With the implementations and patterns covered in this guide, you're well-equipped to handle LCA problems whether they appear in an interview, a competitive programming contest, or a production system dealing with hierarchical data.