Vibe Engines Learn
Algorithms · Trees

Two Nodes, Climbing to Meet.

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.

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

Algorithm

Binary Search Trees →
Algorithm

DFS & Topological Sort →
Algorithm

Segment Trees →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 99 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

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →
Challenges →