What Is Binary Lifting? K-th Ancestor and LCA in O(log n)
- Binary lifting precomputes
up[v][j](the 2^j-th ancestor of node v) in O(n log n), turning any k-th ancestor query into O(log n) - The recurrence
up[v][j] = up[up[v][j-1]][j-1]builds each level by reusing the previous jump, the same doubling trick as binary exponentiation - K-th ancestor queries decompose k into binary and hop through set bits, each costing O(1) via a table lookup
- Binary lifting LCA runs in two phases: equalize depths with a k-th ancestor call, then simultaneously lift both nodes from the top of the table until one step below the common ancestor
- LOG = 20 covers trees up to 10^6 nodes; setting it too low silently corrupts answers on deep trees without raising an error
- LeetCode 1483 (Kth Ancestor of a Tree Node) is a direct binary lifting implementation and the canonical interview problem for this technique
Finding the k-th ancestor of a node in a tree sounds like a simple loop. Walk up k edges. Done. That works until k is 500,000 and you have 100,000 such queries. Binary lifting precomputes a table of 2^j-th ancestors so any ancestor lookup costs O(log n) instead of O(depth). The same table powers one of the fastest practical LCA algorithms.
Two problems. One data structure.
The Problem With Walking Up One Node at a Time
Take a tree with n = 10^6 nodes shaped like a long chain. Find the 500,000th ancestor of the deepest node. Naive approach: walk up 500,000 edges. Run 100,000 such queries and you are at 5 × 10^10 operations. Your code submits. The judge thinks about it. And then it does not accept your answer. It gives you TLE.
Time Limit Exceeded. Congratulations, your loop counted to 5 × 10^10.
Binary lifting trades O(n log n) of upfront work for O(log n) per query, and that deal is almost always worth taking.
The Insight: Every Integer Is a Sum of Powers of 2
That is just binary representation. Your CPU has been doing this since kindergarten. 13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0.
To find the 13th ancestor, you jump up 8, then 4, then 1. Each jump uses a precomputed table entry, so each step costs O(1). Three jumps instead of 13 plodding steps up the tree.
The table is up[v][j]: the 2^j-th ancestor of node v.
up[v][0]= direct parentup[v][1]= grandparent (parent of parent)up[v][2]= 4th ancestorup[v][j]= 2^j-th ancestor
The recurrence that fills the table:
up[v][j] = up[up[v][j-1]][j-1]
"The 2^j-th ancestor of v is the 2^(j-1)-th ancestor of v's 2^(j-1)-th ancestor."
It is the same doubling trick behind binary exponentiation: each level doubles your reach by reusing what you already computed. You are building a cheat sheet, and each page of the cheat sheet is built from the previous page.
A Concrete Example
Work through this tree, rooted at node 1:
1
/ \
2 3
/ \
4 5
/
6
Depths: 1→0, 2→1, 3→1, 4→2, 5→2, 6→3.
With LOG = 3, the ancestor table looks like this. Node 6 is the interesting row.
To find the 3rd ancestor of node 6: k = 3 = 2 + 1 (binary: 11).
- j=0: bit set, jump to
up[6][0]= node 4 - j=1: bit set, jump to
up[4][1]= node 1
Three steps up, two jumps. The answer is node 1. Trace manually: 6 → 4 → 2 → 1. Correct.
Building the Table
BFS fills the table top-down, which guarantees parents are processed before children. Boring, responsible, exactly right.
from collections import deque LOG = 20 # covers trees with up to 2^20 nodes NONE = -1 def build_binary_lifting(n, adj, root): parent = [NONE] * (n + 1) depth = [0] * (n + 1) up = [[NONE] * LOG for _ in range(n + 1)] visited = [False] * (n + 1) visited[root] = True queue = deque([root]) while queue: v = queue.popleft() up[v][0] = parent[v] for j in range(1, LOG): if up[v][j - 1] != NONE: up[v][j] = up[up[v][j - 1]][j - 1] for neighbor in adj[v]: if not visited[neighbor]: visited[neighbor] = True parent[neighbor] = v depth[neighbor] = depth[v] + 1 queue.append(neighbor) return up, depth
The inner loop runs LOG iterations per node, so total preprocessing is O(n × LOG) = O(n log n). Space is the same: one table entry per node per level. You pay once, upfront, and then every query gets to cash in on that investment.
Querying the k-th Ancestor
Once the table exists, decompose k in binary and jump through the set bits.
def kth_ancestor(v, k, up): for j in range(LOG): if (k >> j) & 1: # if bit j is set in k v = up[v][j] if v == NONE: return NONE # k exceeds this node's depth return v
This runs in O(log k). Since k ≤ n, that is O(log n). The interviewer is watching you do this in logarithmic time instead of linear time, and they appreciate it.
Binary Lifting LCA: Two Phases
The Lowest Common Ancestor of nodes u and v is the deepest node that is an ancestor of both. Binary lifting finds it in two phases.
Phase 1: bring the deeper node up to match the shallower node's depth. Call kth_ancestor(deeper_node, depth_difference).
Phase 2: if the nodes are now equal, that is the LCA. Otherwise, binary lift both simultaneously from the top of the table downward. Jump whenever the two nodes' ancestors at level j are different. When no more jumps are possible, the LCA is one step up.
def lca(u, v, up, depth): # phase 1: equalize depths if depth[u] < depth[v]: u, v = v, u u = kth_ancestor(u, depth[u] - depth[v], up) if u == v: return u # phase 2: lift both until one step below the LCA for j in range(LOG - 1, -1, -1): if up[u][j] != up[v][j]: u = up[u][j] v = up[v][j] return up[u][0]
Example: LCA of nodes 6 and 5.
- depth[6] = 3, depth[5] = 2. Lift 6 by 1. Node 6 → node 4.
- u=4, v=5. Different nodes.
- j=1: up[4][1]=1, up[5][1]=1. Same. Skip.
- j=0: up[4][0]=2, up[5][0]=2. Same. Skip.
- Return up[4][0] = node 2. Correct.
Time and Space
| Operation | Time | Space |
|---|---|---|
| Preprocessing | O(n log n) | O(n log n) |
| k-th ancestor query | O(log n) | O(1) |
| LCA query | O(log n) | O(1) |
For n = 10^5 nodes and 10^5 queries, that is about 1.7 million precomputation steps and 1.7 million query steps. The naive approach for the same workload: 10^10. The table pays for itself instantly.
For n = 10^6, the table holds about 20 million integers, roughly 80 MB at 4 bytes each. Worth checking memory limits on resource-constrained problems. Sometimes the tradeoff is space for time, and sometimes the problem is also trying to squeeze you on space. Read the constraints.
The Euler tour + sparse table approach achieves O(1) per LCA query after the same O(n log n) setup. Binary lifting is slightly slower per query but simpler to code under pressure and handles k-th ancestor queries natively. Pick the one you can actually implement in 25 minutes.
Where This Shows Up in Interviews
LCA problems appear at mid-to-upper difficulty. LeetCode 236 has a clean recursive solution that does not need binary lifting. LeetCode 1483 (Kth Ancestor of a Tree Node) is essentially a direct binary lifting implementation.
Variants that demand it:
- Path queries asking for the maximum edge weight between two nodes
- Problems where you need the LCA of dynamically added nodes
- Anything with tight time limits and many ancestor queries
The same "double your reach" intuition underpins the segment tree, the sparse table, and binary search. Once you see it in binary lifting, you start recognizing it everywhere like a pattern you cannot unsee.
If you want to practice explaining this kind of algorithm out loud under interview conditions, SpaceComplexity runs voice-based mock interviews with rubric-based scoring across problem-solving, communication, and code quality. Explaining why the recurrence works is a different skill than coding it, and interviews score both.
Three Things That Trip People Up
When your binary lifting returns -1 on every query and you have been staring at it for 45 minutes.
LOG too small. If n = 10^6 and you set LOG = 15, deep trees silently produce wrong answers because 2^15 = 32,768 does not reach the root. Use LOG = 20. It costs 5 extra entries per node and never costs correctness. Just set it to 20 and stop thinking about it.
Missing the NONE sentinel. When k exceeds a node's depth, the loop should return NONE, not silently read garbage from an uninitialized table entry. Guard every table access. This is the kind of bug that passes sample tests and fails on the deep-chain stress test you did not write.
Asymmetry in phase 2 of LCA. Both nodes must move simultaneously in the binary search. Lifting only one breaks the invariant and lands in the wrong place. Most LCA bugs trace back to this. The symptom is answers that are off by one level, which is the exact kind of subtle wrong that passes partial scoring and fails full scoring.