Binary Lifting
The Core Idea
The naive LCA walks up one parent at a time. If you need to climb 1000 levels, that's 1000 steps. Binary lifting lets you climb in powers of 2: jump 512, then 256, then 128... You reach the same destination in \(\lfloor \log_2 1000 \rfloor + 1 = 10\) jumps.
The technique: precompute, for every node \(v\) and every power \(k\), the \(2^k\)-th ancestor of \(v\). Store it in a table \(up[v][k]\).
Building the Table
Base case: \(up[v][0] = parent[v]\). The \(2^0 = 1\)st ancestor is the parent.
Transition: \(up[v][k] = up[up[v][k-1]][k-1]\).
Read that carefully. The \(2^k\)-th ancestor of \(v\) is the \(2^{k-1}\)-th ancestor of the \(2^{k-1}\)-th ancestor of \(v\). You jump halfway, then jump halfway again. Two jumps of \(2^{k-1}\) equal one jump of \(2^k\).
If any jump lands on the root's parent (node 0 or a sentinel), all further jumps from there also return 0. This handles nodes that don't have a \(2^k\)-th ancestor — they've gone past the root.
Trace on an 8-Node Tree
Parents and depths:
| Node | Parent | Depth |
|---|---|---|
| 1 | 0 (root) | 0 |
| 2 | 1 | 1 |
| 3 | 1 | 1 |
| 4 | 1 | 1 |
| 5 | 2 | 2 |
| 6 | 2 | 2 |
| 7 | 4 | 2 |
| 8 | 5 | 3 |
We need \(MAXLOG = \lceil \log_2 8 \rceil + 1 = 4\) (powers 0, 1, 2, 3 suffice for 8 nodes).
\(k = 0\) (parent):
| Node | \(up[v][0]\) |
|---|---|
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 2 |
| 7 | 4 |
| 8 | 5 |
\(k = 1\) (\(2^1 = 2\)nd ancestor = grandparent):
\(up[v][1] = up[up[v][0]][0]\)
| Node | \(up[v][0]\) | \(up[up[v][0]][0]\) | \(up[v][1]\) |
|---|---|---|---|
| 1 | 0 | \(up[0][0] = 0\) | 0 |
| 2 | 1 | \(up[1][0] = 0\) | 0 |
| 3 | 1 | \(up[1][0] = 0\) | 0 |
| 4 | 1 | \(up[1][0] = 0\) | 0 |
| 5 | 2 | \(up[2][0] = 1\) | 1 |
| 6 | 2 | \(up[2][0] = 1\) | 1 |
| 7 | 4 | \(up[4][0] = 1\) | 1 |
| 8 | 5 | \(up[5][0] = 2\) | 2 |
\(k = 2\) (\(2^2 = 4\)th ancestor):
\(up[v][2] = up[up[v][1]][1]\)
| Node | \(up[v][1]\) | \(up[up[v][1]][1]\) | \(up[v][2]\) |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 |
| 5 | 1 | \(up[1][1] = 0\) | 0 |
| 8 | 2 | \(up[2][1] = 0\) | 0 |
(Other nodes follow the same pattern — all reach 0 since the tree has depth 3.)
The LCA Algorithm
With the table built, here's how to find \(LCA(u, v)\):
Step 1: Equalize depths. If \(depth[u] > depth[v]\), lift \(u\) up by \(depth[u] - depth[v]\) levels. Do this using the binary representation of the difference — jump by powers of 2.
Step 2: If \(u = v\), return \(u\). (One node was an ancestor of the other.)
Step 3: Lift together. For \(k\) from \(MAXLOG - 1\) down to 0: if \(up[u][k] \neq up[v][k]\), set \(u = up[u][k]\) and \(v = up[v][k]\). This keeps \(u\) and \(v\) just below the LCA.
Step 4: Return \(up[u][0]\) — the parent of where we stopped, which is the LCA.
Why iterate from high \(k\) to low? You want to make the largest safe jumps first. A jump is "safe" if \(up[u][k] \neq up[v][k]\) — meaning you haven't overshot the LCA. By going from large to small, you land exactly one level below the LCA.
Trace: LCA(8, 6)
\(depth[8] = 3, depth[6] = 2\). Difference = 1.
Step 1: Lift node 8 by 1. Binary representation of 1 = \(2^0\). So set \(u = up[8][0] = 5\).
Now \(u = 5, v = 6\), both at depth 2. They're not equal.
Step 3: Iterate \(k = 3, 2, 1, 0\):
| \(k\) | \(up[u][k]\) | \(up[v][k]\) | Equal? | Action |
|---|---|---|---|---|
| 3 | 0 | 0 | Yes | skip |
| 2 | 0 | 0 | Yes | skip |
| 1 | 1 | 1 | Yes | skip |
| 0 | 2 | 2 | Yes | skip |
All equal? That means \(u\) and \(v\) already share the same parent. Return \(up[u][0] = up[5][0] = 2\).
\(LCA(8, 6) = 2\). Correct.
Trace: LCA(8, 7)
\(depth[8] = 3, depth[7] = 2\). Difference = 1. Lift 8 by 1: \(u = up[8][0] = 5\).
Now \(u = 5, v = 7\), both at depth 2. Not equal.
Step 3:
| \(k\) | \(up[5][k]\) | \(up[7][k]\) | Equal? | Action |
|---|---|---|---|---|
| 3 | 0 | 0 | Yes | skip |
| 2 | 0 | 0 | Yes | skip |
| 1 | 1 | 1 | Yes | skip |
| 0 | 2 | 4 | No | \(u=2, v=4\) |
After step 3: \(u = 2, v = 4\). Both at depth 1.
Step 4: Return \(up[2][0] = 1\).
\(LCA(8, 7) = 1\). Correct — 8 is in node 2's subtree, 7 is in node 4's subtree, they meet at the root.
Trace: LCA(5, 7)
\(depth[5] = 2, depth[7] = 2\). Already equal.
\(u = 5, v = 7\). Not equal.
| \(k\) | \(up[5][k]\) | \(up[7][k]\) | Equal? | Action |
|---|---|---|---|---|
| 3 | 0 | 0 | Yes | skip |
| 2 | 0 | 0 | Yes | skip |
| 1 | 1 | 1 | Yes | skip |
| 0 | 2 | 4 | No | \(u=2, v=4\) |
Return \(up[2][0] = 1\).
\(LCA(5, 7) = 1\). Correct.
Bonus: Kth Ancestor
Binary lifting also solves: "what is the \(k\)-th ancestor of node \(v\)?"
Decompose \(k\) into binary. For each set bit at position \(b\), jump: \(v = up[v][b]\).
Example: 5th ancestor of node 8. \(5 = 101_2 = 2^2 + 2^0\).
- Jump \(2^0\): \(v = up[8][0] = 5\).
- Jump \(2^2\): \(v = up[5][2] = 0\).
Node 8's 5th ancestor doesn't exist (tree depth is only 3). The result 0 indicates "past the root." In practice, you'd check for this and return -1.
Example: 3rd ancestor of node 8. \(3 = 11_2 = 2^1 + 2^0\).
- Jump \(2^0\): \(v = up[8][0] = 5\).
- Jump \(2^1\): \(v = up[5][1] = 1\).
3rd ancestor of 8 is node 1 (root). Walk it manually: 8 → 5 → 2 → 1. Correct.
The Code
const int MAXLOG = 18;
vector<int> adjacency[200005];
int up[200005][MAXLOG];
int depthOf[200005];
void dfs(int node, int parent) {
up[node][0] = parent;
for (int k = 1; k < MAXLOG; k++) {
up[node][k] = up[up[node][k - 1]][k - 1];
}
for (int child : adjacency[node]) {
if (child != parent) {
depthOf[child] = depthOf[node] + 1;
dfs(child, node);
}
}
}
int lca(int u, int v) {
if (depthOf[u] < depthOf[v]) swap(u, v);
int difference = depthOf[u] - depthOf[v];
for (int k = 0; k < MAXLOG; k++) {
if ((difference >> k) & 1) {
u = up[u][k];
}
}
if (u == v) return u;
for (int k = MAXLOG - 1; k >= 0; k--) {
if (up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
int kthAncestor(int node, int k) {
for (int bit = 0; bit < MAXLOG; bit++) {
if ((k >> bit) & 1) {
node = up[node][bit];
}
}
return node;
}
Complexity: \(O(n \log n)\) preprocessing (table has \(n \times \log n\) entries), \(O(\log n)\) per LCA query, \(O(\log n)\) per \(k\)-th ancestor query.
Memory: \(up[200005][18]\) is about \(3.6 \times 10^6\) integers, roughly 14 MB. Comfortable.
When to Choose Binary Lifting
Binary lifting is the default LCA method in competitive programming. It's easy to code (about 30 lines for the core), handles online queries, and gives you \(k\)-th ancestor for free.
Use Euler tour + RMQ (next lesson) when you need \(O(1)\) per query and don't need \(k\)-th ancestor. Use binary lifting everywhere else.
Try It
Fill in the up table computation and the lca function in the starter code.
Predict before running: On a chain 1 → 2 → 3 → 4 → 5, what is \(up[5][2]\)? That's the \(2^2 = 4\)th ancestor of 5. Walking up: 5 → 4 → 3 → 2 → 1. So \(up[5][2] = 1\).
Challenge: What is \(LCA(u, u)\)? In step 1, the depth difference is 0, so no lifting. In step 2, \(u = v\), so return \(u\). The LCA of any node with itself is itself.
Edge Cases to Watch For
- Kth ancestor where \(k >\) depth: The node doesn't have a \(k\)-th ancestor. The jumps land on the sentinel node 0 (past the root). Your code must detect this and return \(-1\) — otherwise it silently returns the sentinel as a valid node.
- MAXLOG too small: If \(2^{\text{MAXLOG}} < n\), the table can't reach the root from the deepest node. Always set \(\text{MAXLOG} \geq \lceil \log_2 n \rceil + 1\). This is a silent bug — queries return wrong ancestors without any error.
Problems
| Problem | Link | Difficulty |
|---|---|---|
| CSES — Company Queries I | cses.fi/problemset/task/1687 | Medium |
| CSES — Company Queries II | cses.fi/problemset/task/1688 | Medium |
| LC 1483 — Kth Ancestor of a Tree Node | leetcode.com/problems/kth-ancestor-of-a-tree-node | Hard |
| CF 208E — Blood Cousins | codeforces.com/problemset/problem/208/E | Hard |