Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Trees

Two Nodes, Climbing to Meet.

Watch the explainer

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
0
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.

0

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).

1

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.

2

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.

The picture: level, then climb together

012345678910query (10, 6)depth 10 = 4, depth 6 = 2level: 10 jumps 2^1 to 3lift k=3,2,1: both reach 0, skiplift k=0: 3, 6 → 1, 2, jumpparent of 1 and 2 = 0
An eleven-node tree (the page’s own: node 0 is the root and each node’s parent is the one above it). The query is nodes 10 and 6, whose lowest common ancestor is the root. Node 10 is two levels deeper, so it first jumps up 2 to node 3. Then both nodes try the big jumps, find that they land on the same node (0, the root) and skip them, and only the single step differs: 3 and 6 move to 1 and 2, whose parent is 0.

Worked example, step by step

The table is built with 4 levels, because the tree has 11 nodes and ceil(log2 11) = 4. The root is its own ancestor, so up[k][0] = 0 for every k. For the query lca(10, 6) the first phase equalises depth, the second finds the last pair of nodes that still differ. The Pair column shows (u, v) after the step.

PhasekLook atActionPair
start–depth[10] = 4, depth[6] = 2d = 2 = 10 in binary(10, 6)
level0bit 0 of d is 0no jump(10, 6)
level1bit 1 of d is 1u = up[1][10] = 3(3, 6)
level2bit 2 of d is 0no jump(3, 6)
level3bit 3 of d is 0no jump(3, 6)
lift3up[3][3] = 0, up[3][6] = 0equal: skip(3, 6)
lift2up[2][3] = 0, up[2][6] = 0equal: skip(3, 6)
lift1up[1][3] = 0, up[1][6] = 0equal: skip(3, 6)
lift0up[0][3] = 1, up[0][6] = 2differ: jump both(1, 2)
answer–up[0][1] = up[0][2] = 0LCA = 0(1, 2)

Notice how little work the second phase does. The three highest jumps (k = 3, 2, 1) all land on the root for both nodes, so equal ancestors tell us only that the jump goes too far and is skipped; the moment up[k][u] ≠ up[k][v] is the moment a jump is safe. Only k = 0 changes the pair. The loop never needs to know where the LCA is, only that it stays one step above the final pair. The depth difference between the nodes was 2, which is 10 in binary, so one jump of 2¹ levelled them. Distance comes almost for free from the same answer: depth[u] + depth[v] − 2·depth[lca] is 4 + 2 − 2·0 = 6 edges between 10 and 6.

Complexity and trade-offs

n is the number of nodes, q the number of queries. All rows assume a static tree.

CaseTimeSpaceWhy
Binary liftingO(n log n) build, O(log n) per queryO(n log n)Simple, and the same table also answers k-th ancestor and path aggregates. On a 100,000-node path one query took 9 jumps.
Walk up one parent at a timeO(n) per queryO(n)The same query walks 99,998 steps on that path. Fine for a few queries on a shallow tree.
Euler tour + sparse tableO(n log n) build, O(1) per queryO(n log n)Reduces LCA to a range-minimum query over depths. Faster queries, but the table is bigger than the tree needs.
Heavy-light decompositionO(n) build, O(log n) per queryO(n)Jumps along heavy paths instead of powers of two, with only linear memory.
Offline (Tarjan’s LCA)near-linear for all queries togetherO(n + q)Needs every query up front and answers them in one DFS with a union-find.

The cost to watch is the table. With 1,000,000 nodes LOG is 20, so there are 20,000,000 entries, about 80 MB at four bytes each. That is why the linear-memory methods matter on very large trees, and why a one-off query on a small tree is better answered by walking up.

Common mistakes

  • Assuming the first argument is the deeper one

    Without the swap the depth difference is negative and the bit loop jumps nonsense distances. On the page’s tree lca(1, 3) returns 0 while the right answer, which lca(3, 1) returns, is 1.

  • Making the table too short

    If LOG is smaller than ceil(log2 n), deep nodes cannot be levelled. A root with a chain of nine nodes and one extra leaf (11 nodes) needs 4 levels; with 3, lca(9, 10) returns 1 and the right answer is 0.

  • Lifting from the smallest k up

    The second phase must go from the largest jump down, like writing a number in binary from the top bit. Run ascending and lca(7, 9) on the page’s tree returns 1 instead of 0: an early small jump can step over the point where the paths meet.

  • Forgetting the u == v check after levelling

    When one query node is an ancestor of the other, levelling already lands on the answer. Skip the check and the second phase pushes past it: lca(10, 3) returns 1, but node 3 is an ancestor of 10 and is the answer.

  • Filling the table node by node

    up[k][v] needs up[k-1] of an ancestor, so build one level k at a time across all nodes. Looping over nodes first only works if parents always have smaller labels. With parents [3, −1, 3, 1] (node 1 is the root) and 3 levels, lca(0, 2) comes out as 1; the right answer is 3.

Where this shows up

  • Distances and paths in a tree

    The distance between two nodes, whether a node lies on the path between two others, and the maximum or minimum edge weight on a path all reduce to the LCA, plus an extra table of aggregates built beside up.

  • Spanning-tree queries

    After building a minimum spanning tree, the heaviest edge on the tree path between two vertices is found by lifting from each endpoint to their LCA while tracking the maximum weight seen.

  • Biology and family trees

    The most recent common ancestor of two species in a phylogenetic tree, or of two people in a family tree, is their lowest common ancestor.

  • Version control and file systems

    Finding the nearest shared directory of two paths is an LCA in the directory tree. Version-control tools ask a close cousin of the question when they look for the merge base of two commits, although a commit history is a graph rather than a tree, so the table-of-ancestors trick needs care there.

SOLVE IT YOURSELF

Solve it: lowest common ancestor in O(log n)

Walking two nodes up to their meeting point is O(n) per query. Precompute every 2ᵏ-th ancestor and you can jump there in binary — O(log n) per query, forever. Python or TypeScript.

YOUR TASK

Implement build_lca(n, parent, root), which precomputes the jump table and depths, and lca(up, depth, u, v), which answers a query in O(log n).

HINTS — 6 IDEAS
  1. up[k][v] is the 2ᵏ-th ancestor of v. The recurrence is the whole trick: up[k][v] = up[k−1][ up[k−1][v] ] — a 2ᵏ jump is two 2^(k−1) jumps.
  2. Let the root be its own ancestor. That makes over-jumping harmless instead of an out-of-range crash.
  3. To query: first lift the deeper node to the shallower one’s depth. The depth difference in binary tells you exactly which jumps to take.
  4. If they are now the same node, that node is the answer — one is an ancestor of the other.
  5. Otherwise jump both from the largest power down, but only when up[k][u] != up[k][v] — move only while the ancestors still differ.
  6. That leaves both one step below the LCA, so the answer is up[0][u]. Jumping while they are equal would overshoot past it.
CPython · WebAssembly

Keep going

▶  Watch it explained

Binary Lifting (LCA): Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done
NextThe Non-Backtracker: KMP Next in “Advanced Algorithms & Data Structures” · step 6 of 13

Explore the topic

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

More Algorithms