Lowest common ancestor: Definition & Examples

The lowest common ancestor (LCA) of two nodes in a rooted tree is the deepest node that lies on both paths to the root. In a trading firm’s reporting tree, it identifies the most specific reporting unit that contains both queried books. Each path includes its starting node, so a node can be its own ancestor. Competitive Programmer’s Handbook, §18.3

Where two reporting paths meet

Take a fictional reporting tree rooted at node 0. In node order from 0 through 7, the parent array is $(-1,0,0,1,1,3,5,6)$ , with $-1$ marking the root’s missing parent. The paths upwards are

\begin{aligned} 7 &\to 6 \to 5 \to 3 \to 1 \to 0, \\ 4 &\to 1 \to 0. \end{aligned}

Both paths include 1 and 0. Node 1 is one edge from the root, so it is deeper than node 0 and $\operatorname{LCA}(7,4)=1$ . The dashed segment in the diagram is the shared path above that first meeting point.

In a fictional tree rooted at node 0, the paths from nodes 7 and 4 first meet at node 1 at depth 1. Both paths continue to node 0 at depth 0.

The solid blue branches meet at the root of the smallest reporting subtree that contains both query nodes.

If you query nodes 7 and 3, the answer is 3 because the path from 7 already passes through 3. These answers are relative to the chosen root and parent links. If a book reports to several units, specify the reporting hierarchy first. The unique tree answer assumes each non-root node has exactly one parent and both nodes belong to the same tree.

Walk the parents or precompute jumps

With depths available, raise the deeper node until both are at the same depth, then move both up one parent at a time until they coincide. Node 7 starts at depth 5 and node 4 at depth 2, so raise 7 by three edges to node 3. Nodes 3 and 4 then meet at their parent, node 1. A parent walk takes

O(h+1)

time in the worst case for a tree of height

h

. If the input is an edge list, the SelfMadeQuant lesson Breadth-First and Depth-First Search shows how to record parents and depths in a traversal from the root. The public page is a preview. The full lesson requires membership.

For repeated queries on a fixed tree, binary lifting stores each node’s ancestors at distances of 1, 2, 4 and so on. To align nodes 7 and 4, use

3=2+1

to jump from 7 to 5 and then to 3. If the aligned nodes already coincide, return that node. Otherwise, try paired jumps from largest to smallest. Take a jump only if both landings exist and are distinct. This keeps both nodes below the first common ancestor. Once no such jump remains, their parent is the answer. Here, even the one-edge jump from 3 and 4 would put both at 1, so return 1.

For

n

nodes, the jump table costs

O(n\log n)

time and space to build and answers queries in

O(\log n)

time. More specialised LCA algorithms can reduce those bounds to linear preprocessing time and space and constant query time. Competitive Programmer’s Handbook, §18.3, Schieber and Vishkin

Sources

Antti Laaksonen, Competitive Programmer’s Handbook, §18.3, defines the query and describes the depth-alignment and jump method.
Baruch Schieber and Uzi Vishkin, On Finding Lowest Common Ancestors: Simplification and Parallelization, gives the preprocessing and query bounds for a specialised LCA algorithm.

Where two reporting paths meet

Walk the parents or precompute jumps

Sources

Related terms

Binary lifting