Binary Lifting and Sparse LCA

The recursive LCA on the previous page is $O(n)$ per query and that is the right answer — for one query. Change the problem to “answer $10^5$ LCA queries on this tree” and $O(nq)$ becomes $10^{10}$ operations, so the shape of the solution has to change: pay once to preprocess, then answer each query in logarithmic time.

Binary lifting is the standard way to do that, and its idea is one sentence: store, for every node, its $2^k$ -th ancestor for every power of two. Then any jump of $k$ steps is the binary representation of $k$ , executed one power at a time — 13 steps up is $8 + 4 + 1$ , three table lookups instead of thirteen parent hops. LCA follows immediately: level the two nodes, then jump both upward together as far as you can without meeting.

The reason this earns a page rather than a paragraph is that the pattern it teaches — precompute powers of two so that any distance decomposes into $O(\log n)$ jumps — reappears in sparse tables for range minimum, in the $k$ -th ancestor problems, in cycle-finding on functional graphs, and in the “successor after $k$ operations” family. Learning it here means recognising it later.

What you’ll learn

The jump table up[k][v], how it is built in $O(n \log n)$ , and the recurrence that builds level $k$ from level $k-1$ in one line.
The two-phase LCA query: level, then descend the powers from high to low, and why the loop must go high-to-low.
Why the up[k][a] != up[k][b] test — rather than == — is the correct condition, and what it leaves you holding at the end.
The cost model that decides between recursion, binary lifting, and Euler-tour + sparse table.

The cue

The problem gives one tree and many queries: “answer $q$ queries of the form LCA(u, v) / the k-th ancestor of u / the distance between u and v”, with $q$ up to $10^5$ .
You need the $k$ -th ancestor of a node, for arbitrary $k$ — the direct request, LC 1483.
Something must be repeated $k$ times where $k$ is huge and the operation is a function — “where does this pointer land after $10^9$ steps” — because functional-graph jumping is the same table.
A tree query needs a value along the path (max edge, sum, min) and you can store it alongside the jump table, one array per power.

The reframe: the expensive thing is walking up one step at a time. Precompute power-of-two shortcuts and every distance becomes at most $\log n$ shortcuts, because every integer is a sum of distinct powers of two. That is the entire technique; the LCA procedure is an application of it.

Reach for something else when there is a single query (plain recursive LCA, $O(n)$ , no preprocessing), when the tree is a BST and the query is LCA (the BST property gives $O(h)$ with no tables), when the tree changes between queries (link-cut trees or Euler tour with a BIT), or when you need $O(1)$ per query and can afford the setup — Euler tour plus a sparse table gets you there.

Visual intuition

Start with the baseline this replaces: the single-query recursive LCA, which touches every node once.

treeThe O(n) baseline: recursive LCA visits the whole tree onceLC 236 · O(n) per query

1def lca(node, p, q):2    if node is None or node.val in (p, q):3        return node4    left  = lca(node.left,  p, q)5    right = lca(node.right, p, q)6    if left and right:7        return node          # p and q split here → this is the LCA8    return left or right     # both targets on one side

node5

found5 is one of the two targets. Return it upward — the recursion does not need to search below a target, because any node below it would have this node as its ancestor anyway.

1/4

Fine for one query. Repeat it 10^5 times on a 10^5-node tree and it is 10^10 operations -- the point at which the jump table below stops being over-engineering.

Now the table that replaces it. For the tree

text

        0
      /   \
     1     2
    / \   / \
   3   4 5   6
      /
     7
    /
   8

up[k][v] is v’s $2^k$ -th ancestor, and -1 means “past the root”:

node	depth	`up[0]` (parent)	`up[1]` (2 up)	`up[2]` (4 up)	`up[3]` (8 up)
0	0	−1	−1	−1	−1
1	1	0	−1	−1	−1
2	1	0	−1	−1	−1
3	2	1	0	−1	−1
4	2	1	0	−1	−1
5	2	2	0	−1	−1
6	2	2	0	−1	−1
7	3	4	1	−1	−1
8	4	7	4	0	−1

Each column is computed from the one before it by composing it with itself: up[k][v] = up[k-1][ up[k-1][v] ]. Two jumps of $2^{k-1}$ make one jump of $2^k$ — that identity is the whole construction, and it is why the table costs $O(n \log n)$ and not $O(n^2)$ .

Read the table to answer “the 3rd ancestor of 8”: $3 = 2 + 1$ , so up[1][8] = 4, then up[0][4] = 1. Two lookups, and the answer is 1. Checking by hand: 8 → 7 → 4 →

The template

binary_lifting.py

from collections import deque
 
 
class LCA:
    """One tree, many queries. O(n log n) preprocess, O(log n) per query."""
 
    def __init__(self, n, edges, root=0):
        self.n = n
        self.LOG = max(1, n.bit_length())          # enough powers to cover any depth
        adj = [[] for _ in range(n)]
        for a, b in edges:
            adj[a].append(b)
            adj[b].append(a)
 
        self.depth = [0] * n
        self.up = [[-1] * n for _ in range(self.LOG)]
 
        # BFS from the root fills depth and up[0] (the parent). Use BFS, not
        # recursion: a 10^5-node path would blow CPython's frame limit.
        seen = [False] * n
        seen[root] = True
        q = deque([root])
        while q:
            v = q.popleft()
            for u in adj[v]:
                if not seen[u]:
                    seen[u] = True
                    self.up[0][u] = v
                    self.depth[u] = self.depth[v] + 1
                    q.append(u)
 
        # Each level is the previous level composed with itself.
        for k in range(1, self.LOG):
            for v in range(n):
                mid = self.up[k - 1][v]
                self.up[k][v] = -1 if mid == -1 else self.up[k - 1][mid]
 
    def kth_ancestor(self, v, k):
        """The k-th ancestor of v, or -1 if it does not exist."""
        for b in range(self.LOG):
            if k >> b & 1:                          # k in binary, one bit at a time
                v = self.up[b][v]
                if v == -1:
                    return -1
        return v
 
    def lca(self, a, b):
        if self.depth[a] < self.depth[b]:
            a, b = b, a                             # a is the deeper one
        # Phase 1: lift a to b's depth. The difference in binary picks the jumps.
        diff = self.depth[a] - self.depth[b]
        for k in range(self.LOG):
            if diff >> k & 1:
                a = self.up[k][a]
        if a == b:
            return a                                # b was an ancestor of a
        # Phase 2: jump both up together, largest power first, only while the
        # ancestors DIFFER. This lands both on the LCA's children.
        for k in reversed(range(self.LOG)):
            if self.up[k][a] != self.up[k][b]:
                a, b = self.up[k][a], self.up[k][b]
        return self.up[0][a]
 
    def dist(self, a, b):
        return self.depth[a] + self.depth[b] - 2 * self.depth[self.lca(a, b)]
 
 
tree = LCA(9, [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6), (4, 7), (7, 8)])
print([tree.lca(a, b) for a, b in ((3, 4), (8, 3), (5, 6), (8, 6), (0, 8), (7, 4))])
# expect [1, 1, 2, 0, 0, 4]
print([tree.dist(a, b) for a, b in ((3, 4), (8, 3), (5, 6), (8, 6), (0, 8), (7, 4))])
# expect [2, 4, 2, 6, 4, 1]
print(tree.kth_ancestor(8, 3), tree.kth_ancestor(8, 9))   # expect 1 -1

Two design decisions in there are worth defending out loud:

BFS, not recursion, to fill up[0]. A path-shaped tree of $10^5$ nodes is a legal input and CPython’s recursion limit is 1000. Interviewers notice.
self.LOG = n.bit_length(). One power per bit of $n$ is always enough, because no depth exceeds $n-1$ . Sizing it to the actual height is a micro-optimisation; sizing it too small is a wrong answer on deep trees.

Dry run

lca(8, 6) on the tree above. Depths: depth[8] = 4, depth[6] = 2.

Phase 1 — level the deeper node. diff = 4 - 2 = 2 = binary 10, so only bit 1 is set: one jump of $2^1$ .

bit	set?	jump	`a`
0 (1 step)	no	—	8
1 (2 steps)	yes	`up[1][8] = 4`	4

Now a = 4, b = 6, both at depth 2, and they are different — so the LCA is strictly above both.

Phase 2 — descend the powers, high to low, jumping only while the ancestors differ.

`k`	`up[k][4]`	`up[k][6]`	differ?	action	`a`, `b`
3 (8 up)	−1	−1	no (both −1)	do not jump	4, 6
2 (4 up)	−1	−1	no	do not jump	4, 6
1 (2 up)	0	0	no — this is the LCA, jumping would overshoot	do not jump	4, 6
0 (1 up)	1	2	yes	jump both	1, 2

Both nodes are now children of the answer, so return up[0][1] = 0. And indeed LCA(8, 6) = 0: the paths are 8→7→4→1→0 and 6→2→0.

Three things the trace makes visible that the code does not:

The loop must run high-to-low. Each accepted jump is the largest that still keeps the two nodes below the LCA — a greedy binary decomposition of the unknown distance to the LCA. Low-to-high would take a small step first and then be unable to correct, exactly as reading a binary number backwards fails.
The condition is !=, not ==. We deliberately never jump to the LCA, because at level $k$ “the ancestors are equal” only tells you the LCA is at or below that height — it might be much lower. Jumping only while they differ means we can never overshoot, and we end holding the LCA’s two children. The final up[0][a] is the one guaranteed step.
-1 entries make the guard work for free. At $k = 2$ and $k = 3$ both jumps are past the root, so both are -1, so they compare equal and no jump happens. No bounds check needed — but only because “past the root” is a single sentinel value. Storing the root as its own parent instead would silently break this test.

Complexity

Approach	Preprocess	Per query	When it wins
Recursive LCA (LC 236)	none	$O(n)$	one or a few queries
BST LCA (LC 235)	none	$O(h)$	the tree is a BST
Binary lifting	$O(n \log n)$ time and space	$O(\log n)$	many queries, static tree
Euler tour + sparse table	$O(n \log n)$	$O(1)$	very many queries, and you need the constant
Tarjan’s offline LCA	$O(n + q)$ near-linear	—	all queries known upfront

The break-even is worth being able to compute in the room: binary lifting costs about $n \log n$ up front to save $n - \log n$ per query, so it pays off once $q \gtrsim \log n$ — around 17 queries on a $10^5$ -node tree. Effectively: two queries or more, and it is already a defensible choice; a hundred and it is the only one.

Memory is the real constraint. up is $n \log n$ integers — at $n = 10^5$ that is about $1.7 \times 10^6$ entries, fine; at $n = 10^7$ it is not. That is when the Euler-tour formulation, which stores $O(n \log n)$ shorts over an array of size $2n$ , or an $O(n)$ scheme, starts to matter.

The variant map

Problem / variant	What changes
LC 1483 K-th ancestor of a tree node	the table is the answer — no LCA needed, just the bit decomposition of `k`
LC 236 LCA of a binary tree	one query, so plain recursion beats this; binary lifting only if the follow-up adds queries
LC 235 LCA of a BST	the BST property gives the answer in $O(h)$ with no table at all
LC 1650 LCA with parent pointers	two-pointer “cycle” trick in $O(h)$ and $O(1)$ space; the same as intersecting two linked lists
LC 2096 Directions between two nodes	find the LCA, then it is `"U" * (depth[start] - depth[lca])` followed by the root-to-dest path suffix
Distance between two nodes	$depth[a] + depth[b] - 2 \cdot depth[lca]$
Max edge weight on a path	store `mx[k][v]` alongside `up[k][v]` and take the max of the same jumps you already make
K-th node on the path from a to b	split at the LCA: if `k` is within the upward leg, lift from `a`; otherwise lift from `b` by the remaining distance
“After $10^9$ steps” on a functional graph	the same table over `next[v]` instead of `parent[v]`; the graph need not be a tree
Tree changes between queries	binary lifting is static — use Euler tour with a BIT, or link-cut trees

The alongside-the-table variants are the reason this generalises so well: the jumps are fixed, so any associative quantity along the path can ride along at no extra asymptotic cost.

Pitfalls

LOG too small. Sizing the table by the expected height rather than n.bit_length() fails on a path-shaped tree, and only on that input.
Recursion to fill the parent array. A $10^5$ -node path is a legal tree and CPython raises RecursionError past ~1000 frames. Use BFS or an explicit stack.
== instead of != in phase 2. Jumping while the ancestors are equal overshoots and returns something above the LCA. The condition is deliberately “still different”.
Looping low-to-high in phase 2. The greedy decomposition only works from the largest power down.
Forgetting the a == b early return after levelling. If b is an ancestor of a, phase 2 finds nothing to jump and up[0][a] returns b’s parent — off by one level, and only on ancestor-descendant pairs.
Using the root as its own parent instead of -1. The up[k][a] != up[k][b] test relies on out-of-range jumps collapsing to one shared sentinel. Self-parenting makes two different out-of-range jumps compare unequal, and phase 2 takes a jump it should not.
Rebuilding the table per query. The whole point is one preprocess. If the constructor is inside the query loop the solution is $O(qn \log n)$ , worse than the naive version it replaced.
Reaching for it on a single query. $O(n)$ recursion is shorter and has no memory cost. Name the query count before choosing.

Interview follow-ups

They ask	What they’re checking	The answer
“Why powers of two?”	Whether you see the decomposition	Every integer is a sum of distinct powers of two, so any $k$ -step jump is at most $\log k$ table lookups. And each power is built by composing the previous one with itself, which is why the table costs $O(n \log n)$
“Why high-to-low in phase 2?”	Understanding, not memorisation	It is a greedy binary search on the distance to the LCA: take the largest jump that keeps both nodes strictly below it. A small jump first cannot be undone
“Why jump while the ancestors differ?”	The subtle part	Equal ancestors at height $2^k$ only prove the LCA is at or below there, not that it is exactly there. Never jumping to it means never overshooting, and both nodes end on the LCA’s children — so one final parent step is the answer
“How many queries make this worth it?”	Cost modelling	Break-even is around $q \approx \log n$ , so about 17 on a $10^5$ -node tree. Below that, plain recursion; well above it, this
“Can you get O(1) per query?”	Breadth	Yes — Euler tour to reduce LCA to range-minimum, then a sparse table. $O(n \log n)$ preprocess, $O(1)$ query. Binary lifting is easier to write correctly and usually enough
“The tree gains and loses edges between queries”	Boundaries	Binary lifting assumes a static tree. Dynamic connectivity needs Euler tour with a BIT, or link-cut trees for full dynamism
“Now give me the maximum edge weight on the path”	Whether the idea generalises	Store `mx[k][v]` next to `up[k][v]` and combine along the same jumps. Any associative path quantity works this way at no extra cost
“Same technique on a non-tree?”	Pattern recognition	Yes — on any functional graph (each node one outgoing edge), the table answers “where am I after $k$ steps” in $O(\log k)$ , which is how the $10^9$ -iterations problems are solved

Practice

6 problems

0 easy5 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

236Lowest Common Ancestor of a Binary TreemediumLeetCode Top Interview 150metaamazonmicrosoftapple
235Lowest Common Ancestor of a Binary Search TreemediumNeetCode 150Blind 75
1123Lowest Common Ancestor of Deepest Leavesmedium
1650Lowest Common Ancestor of a Binary Tree IIIpremiummedium
2096Step-By-Step Directions From a Binary Tree Node to Anothermedium
1483Kth Ancestor of a Tree Nodehard

Exercises

LC 1483 — Kth Ancestor of a Tree Node · Hard

LCA in O(log n) per query, on a tree given as edges · Hard

LC 2096 — Step-By-Step Directions From a Binary Tree Node to Another · Medium

Self-check

pch.quizTag Binary lifting — self-check

How is level k of the jump table built?

pch.quizShowAnswer

B — By composing level k−1 with itself: up[k][v] = up[k−1][up[k−1][v]] — two jumps of 2^(k−1) make one of 2^k — That composition is why the whole table costs O(n log n) rather than O(n²), and it is the sentence to say first when asked how binary lifting works.
In phase 2 of the LCA query, why jump only while `up[k][a] != up[k][b]`?

pch.quizShowAnswer

B — Because equal ancestors at height 2^k only prove the LCA is at or below that height — never jumping to it guarantees no overshoot, and both nodes end on the LCA's children — The `!=` version can never pass the LCA, so after the loop one parent step from either node is the answer. Using `==` overshoots and returns an ancestor of the LCA.
Why must the phase-2 loop run from the highest power down to the lowest?

pch.quizShowAnswer

B — Because it is a greedy binary decomposition of the unknown distance to the LCA: take the largest jump that still keeps both nodes below it, then refine — Taking a small jump first can leave a remaining distance no combination of the remaining powers can express — the same reason you read a binary number from the most significant bit when decomposing greedily.
You omit the `if a == b: return a` check after levelling the two nodes. What breaks?

pch.quizShowAnswer

B — Ancestor-descendant pairs: phase 2 finds nothing to jump, and up[0][a] returns one level too high — It fails only when one node is an ancestor of the other, which is easy to miss in testing. LCA(0, 8) and LCA(7, 4) are the pairs that catch it.
Roughly how many queries justify the O(n log n) preprocess?

pch.quizShowAnswer

B — About log n — around 17 on a 10^5-node tree; below that plain O(n) recursion is the better answer — Preprocessing costs n log n and each query saves about n, so the crossover is near log n. Naming the query count before choosing the approach is the actual skill being tested.
Why store `-1` for out-of-range jumps rather than making the root its own parent?

pch.quizShowAnswer

B — Because phase 2's equality test relies on all out-of-range jumps collapsing to one shared sentinel — self-parenting makes two different overshoots compare unequal, so the loop takes a jump it should not — This is a genuinely subtle one: with a self-parenting root the `!=` test can be true for two nodes whose jumps both left the tree, and the walk moves when it should stay put.

Recall card

Cue — one static tree, many ancestor or LCA queries; or a $k$ -th ancestor request; or “after $k$ steps” on a functional graph.
Table — up[0][v] = parent(v), then up[k][v] = up[k-1][up[k-1][v]]. Size n.bit_length() powers. -1 means past the root.
K-th ancestor — walk the set bits of $k$ , jumping by up[b], returning −1 on overshoot.
LCA — level the deeper node by the set bits of the depth difference; if they coincide, done; else jump both from the highest power down while the ancestors differ; answer is up[0][a].
Distance — $depth[a] + depth[b] - 2\,depth[lca]$ .
Cost — $O(n\log n)$ preprocess and space, $O(\log n)$ per query. Worth it from roughly $\log n$ queries up.
Fill up[0] with BFS, never recursion — a path of $10^5$ nodes is a legal tree.

Recap

Binary lifting precomputes $2^k$ -th ancestors so any upward distance becomes at most $\log n$ jumps. Every integer is a sum of powers of two; the table lets you spend one lookup per power.
Each level of the table is the previous level composed with itself, which is what keeps the construction to $O(n\log n)$ .
The LCA query is level-then-descend, high power to low, jumping only while the ancestors differ so it can never overshoot. The two clauses people drop are the early a == b return and the -1 sentinel discipline.
It is a static-tree technique, and it generalises twice: any associative quantity can ride alongside the jumps, and the same table answers ” $k$ steps along a functional graph” for non-trees.
Choose it on the query count, not on instinct — and say the number out loud.

Next: Lowest Common Ancestor revisited in the design round — or onwards to graphs, where the same “precompute powers” idea reappears as the sparse table for range minimum queries.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading