What is the lowest common ancestor (LCA)?

The lowest common ancestor of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both — the point where the paths from u and v up to the root first merge. It's a building block for many tree algorithms, including distance between nodes and range queries on trees.

How does binary lifting answer an LCA query?

Two phases. First, lift the deeper node up until both nodes are at the same depth, using power-of-two jumps. If they're now the same node, that's the LCA. Otherwise, lift both nodes simultaneously by the largest jumps that keep their ancestors different; when no jump keeps them apart, their common parent is the LCA. Each phase is O(log n).

What are the time and space costs?

Preprocessing builds the 2^k-ancestor table in O(n log n) time and space. After that, each LCA query is O(log n). This preprocess-once, query-fast trade-off is why binary lifting is a standard choice when you must answer many LCA (or k-th ancestor) queries on a static tree.

Algorithms · Trees

Two Nodes, Climbing to Meet.

Q: What is binary lifting?

Binary lifting precomputes, for every node, its 2^k-th ancestor for each k (its parent, grandparent's-grandparent, and so on in powers of two). With that table you can jump up any number of levels by decomposing the distance into powers of two, so moving up d levels takes O(log d) jumps instead of d steps.

Two nodes in a tree; where do their paths to the root first join? That’s the lowest common ancestor. Walking up one level at a time is O(depth). Binary lifting precomputes each node’s 2ᵏ-th ancestor, so you leap up the tree in powers of two — level the deeper node, then lift both together — and answer LCA in O(log n).

O(log n) per query · O(n log n) preprocess · trees

ancestor table

up[k][v] = the 2ᵏ-th ancestor of v — parent, grandparent, …

level up

Lift the deeper node until both are at the same depth.

lift together

Jump both nodes up by the largest power that keeps them apart.

the meet

When no jump keeps them apart, their shared parent is the LCA.

lca.js — level the deeper, then lift both

query: 10 & 8 10 & 6 9 & 4 9 & 10

Ready

Find the LCA of two nodes (blue and red). Press Step: first we lift the deeper node up by powers of two until both sit at the same depth, then lift both together until they land on their shared ancestor.

–

phase

jumps

–

LCA

How it works

Two ideas. First, if you know each node’s ancestor at every power-of-two distance, you can move up any number of levels by writing that number in binary and taking one jump per set bit — up d levels in O(log d). Second, the LCA query decomposes into two clean phases using exactly that power.

Precompute the table

up[0][v] is v’s parent; up[k][v] = up[k-1][ up[k-1][v] ] — the 2ᵏ ancestor is the 2^(k-1) ancestor of the 2^(k-1) ancestor. O(n log n).

Level the depths

Say u is deeper by d. Jump u up 2ᵏ for each set bit of d, so u and v end at the same depth. If u == v now, that’s the LCA.

Lift both together

From the highest k down: if up[k][u] ≠ up[k][v], jump both up 2ᵏ (they’re still below the LCA). Otherwise skip — that jump would overshoot.

✓

The parent is the answer

After the loop, u and v are the two children just below the LCA, so up[0][u] (their shared parent) is the LCA.

Query

O(log n)

Preprocess

O(n log n)

Space

O(n log n)

Naive walk

O(n)

The code

# up[k][v] = 2^k-th ancestor; LOG = ceil(log2(n)) def lca(u, v): if depth[u] < depth[v]: u, v = v, u # make u the deeper d = depth[u] - depth[v] for k in range(LOG): # level u up to v's depth if (d >> k) & 1: u = up[k][u] if u == v: return u for k in reversed(range(LOG)): # lift both together if up[k][u] != up[k][v]: u, v = up[k][u], up[k][v] return up[0][u] # shared parent

The same table answers "k-th ancestor of v" and, with a depth array, "distance between u and v" (= depth[u] + depth[v] − 2·depth[lca]). Binary lifting is the workhorse for static trees; for very heavy query loads, Euler-tour + sparse-table RMQ gives O(1) queries after O(n log n) preprocessing.

Quick check

1. Why lift the deeper node to equal depth first?

2. In phase 2, why jump only when up[k][u] ≠ up[k][v]?

FAQ

What is the lowest common ancestor?

The deepest node that is an ancestor of both query nodes — where their upward paths to the root first merge.

What is binary lifting?

Precomputing each node's 2ᵏ-th ancestor for all k, so you can jump up any number of levels in O(log n) by decomposing the distance into powers of two.

What are the costs?

O(n log n) preprocessing (time and space), then O(log n) per query. Ideal for many queries on a static tree.

Any faster alternatives?

Euler-tour plus sparse-table range-minimum gives O(1) per query after O(n log n) preprocessing; Tarjan's offline LCA is near-linear if all queries are known upfront.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

Two Nodes, Climbing to Meet.

How it works

Precompute the table

Level the depths

Lift both together

The parent is the answer

The code

Quick check

FAQ

Keep going

Explore the topic

More Algorithms

Explore more from Vibe Engines

How it works

Precompute the table

Level the depths

Lift both together

The parent is the answer

The code

Quick check

FAQ

Keep going

Binary Search Trees →

DFS & Topological Sort →

Segment Trees →

The DSA Roadmap →

Explore the topic

More Algorithms

Explore more from Vibe Engines

Get the next one in your inbox.