cf.completefrontend
TREES & TRIES · ADVANCED

Binary lifting

Precompute each node's ancestors 1, 2, 4, 8, ... steps up, so you can jump any number of steps up a tree in about log n hops.

Time O(n log n) to build, O(log n) per querySpace O(n log n)2 practice problemsStep-through picture

The idea

Walking up a tree one parent at a time is slow when the tree is deep and you must answer many questions like "who is 1,000 levels above this node?". Each answer could take 1,000 steps.

Binary lifting prepares a table first. up[0][v] is the parent of v. up[1][v] is the node 2 steps up, up[2][v] is 4 steps up, and in general up[j][v] is 2^j steps up. Each row is built from the row before it: going 2^j steps up is going 2^(j-1) steps up, twice.

Any number k is a sum of powers of two (its binary digits). To go k steps up, take one jump for each 1 bit of k. For k = 13, which is 8 + 4 + 1, you take three jumps instead of thirteen steps.

An everyday example

Express elevators in a tall building

A building has elevators that only go up exactly 1, 2, 4, 8, or 16 floors. To go up 13 floors you don't press 13 times. You take the 8-floor elevator, then the 4-floor one, then the 1-floor one. Any trip is a few rides, and the building planner only had to set up a few elevators per floor.

How the example maps to the code
In the exampleIn the code
The elevator going up 2 to the j floorsup[j]
Setting up a longer elevator from two shorter ridesprev[half], two jumps of 2^(j-1)
Splitting 13 into 8 + 4 + 1the bits of k, checked with (k >> j) & 1
Riding one elevatornode = up[j][node]
Going above the roof-1

From the slow way to binary lifting

  1. To find the k-th ancestor of a node, the obvious way is to follow parent k times. That's O(k) per question, up to O(n) on a deep tree. With 100,000 questions on a chain of 100,000 nodes, that can be billions of steps.
  2. The other extreme is a full table: for every node, store every one of its ancestors, so any question is one lookup. But on a chain that's about n² / 2 entries, 5 billion for 100,000 nodes. We need something between "store nothing" and "store everything".
  3. Any k can be written as a sum of powers of two, which is what its binary digits say: 5 = 4 + 1. So if every node knew its ancestor 1, 2, 4, 8, and so on steps up, any climb of k steps could be done with one stored jump per 1 bit, about log k jumps. That's only about log n stored values per node.
  4. Those jumps are also cheap to fill in: going 2^j steps up is going 2^(j-1) steps up twice, so row j of the table comes from row j - 1 with one lookup per node. Build the rows once, then answer each question by jumping along the bits of k. That table of power-of-two jumps is binary lifting.

How it works

  1. Row 0 of the table is the parent array itself, with -1 for the root's parent.
  2. Pick levels, the number of rows, so that 2^levels is bigger than the number of nodes.
  3. Build row j from row j - 1: the node 2^j steps up from v is prev[prev[v]]. If the first half already went past the root (-1), the result is -1 too.
  4. To find the k-th ancestor, first return -1 if k is at least the number of nodes, since no path is that long.
  5. For each bit j of k that is 1, jump: node = up[j][node].
  6. If a jump gives -1, the ancestor doesn't exist, so return -1. Otherwise return node after all jumps.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function buildLifting(parent) {
  2. const n = parent.length;
  3. const levels = Math.max(1, Math.ceil(Math.log2(n + 1)));
  4. const up = [parent.slice()];
  5. for (let j = 1; j < levels; j++) {
  6. const prev = up[j - 1];
  7. up.push(prev.map((half) => (half === -1 ? -1 : prev[half])));
  8. }
  9. return up;
  10. }
  12. function kthAncestor(up, node, k) {
  13. if (k >= up[0].length) return -1;
  14. for (let j = 0; j < up.length; j++) {
  15. if ((k >> j) & 1) node = up[j][node];
  16. if (node === -1) return -1;
  17. }
  18. return node;
  19. }

How fast it is

TimeO(n log n) to build, O(log n) per query
Extra memoryO(n log n)

The table has about log n rows with n entries each, and each entry is one lookup to fill. A query does at most one jump per row.

  • Best caseO(1)

    k >= n, so line 13 returns -1 before any jump.

  • Average caseO(log n)

    A typical query checks each of the about log₂ n rows once.

  • Worst caseO(log n)

    A valid k whose path stays inside the tree: every row is checked, 20 rows for a million nodes. Building the table costs O(n log n), once.

Common mistakes

  • Building row j from the original parent array instead of row j - 1. Each row must double the jump of the row before.
  • Reading prev[-1] when the first half already left the tree. Check for -1 before using it as an index.
  • Making too few rows, so the high bits of k are ignored and the answer is too low in the tree. Size levels from n.
  • Using binary lifting for a single question. Building the table is O(n log n); walking up once is O(n).

When to use it

Look for these clues in a problem:

  • Many queries ask for the k-th ancestor, or the node a certain number of levels up.
  • Many queries ask for the lowest common ancestor in a large, fixed tree.
  • The tree is given as a parent array, and walking up one step at a time would be too slow.
  • The tree doesn't change between queries, so preparing a table once pays off.

Check yourself

Answer each one in your head first, then open it.

Why is row j built from row j - 1 and not from parent?

Row j - 1 already jumps 2^(j-1) steps, so using it twice doubles the jump with one lookup. Using parent would take 2^j lookups per entry.

How many jumps does kthAncestor make for k = 13?

Three, one per 1 bit: 13 is 1101 in binary, so the jumps are 8, 4, and 1.

In the trace, why is row 3 all -1?

Row 3 jumps 8 steps, and the deepest node, 6, has only 5 ancestors.

Why does levels depend on n and not on the tree's height?

It's a simple size that's always safe: any useful k is below n, so Math.ceil(Math.log2(n + 1)) rows cover every bit. Sizing by height saves memory on shallow trees, but needs the depths first.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The table's rule: up[j][v] is the node exactly 2^j steps above v, or -1 if there is none. Row 0 is parent, so it holds there. If row j - 1 holds, then in row j, half = prev[v] is 2^(j-1) steps up, and prev[half] is another 2^(j-1) steps up, 2^j in total. If half is already -1, the longer jump also leaves the tree, so -1 is right.

The query's rule: after handling bits 0 to j, node is the ancestor exactly as many steps above the start as those low bits of k add up to, unless the loop has already returned -1. Each 1 bit adds its jump of 2^j, each 0 bit adds nothing, and climbs up a tree add up the same in any order, so after the last bit node is exactly k steps up.

Because levels is chosen so that 2^levels > n, and line 13 ensures k < n, every 1 bit of k has a row, so no part of the climb is lost. The loop runs levels times, about log₂ n, and stops early the moment it leaves the tree, since nothing can be reached from above the root.

Going deeper

3 more ideas

Why the jumps add up correctly

Writing k in binary splits it into distinct powers of two, like 13 = 8 + 4 + 1. Going up is the same no matter the order of the jumps, so taking the jumps for each 1 bit moves exactly k steps. Each jump is one table lookup, so it costs about log k lookups.

Lowest common ancestor with the table

Store each node's depth. First lift the deeper node up until both are at the same depth. If they are now the same node, that is the LCA. Otherwise, for j from the biggest row down to 0, if up[j][a] !== up[j][b], jump both. They end just below the LCA, so the answer is up[0][a]. Each query takes O(log n).

Time and memory

The table has about log n rows of n entries, so building it takes O(n log n) time and memory. After that, each query is O(log n). This pays off when there are many queries; for one query, walking up the parents directly is simpler.

Work it by hand

Every step in a table, with why

Build the table for an 8-node tree, then ask for the 5th ancestor of 6, the 4th ancestor of 7 (which doesn't exist), and the 9th ancestor of 6.

parent = [-1, 0, 1, 1, 3, 4, 5, 2]; kthAncestor(up, 6, 5), kthAncestor(up, 7, 4), kthAncestor(up, 6, 9)

StepStepjRow j, or node before and afterWhat happensWhy
1build0[-1, 0, 1, 1, 3, 4, 5, 2]a copy of parentn = 8, so levels = Math.ceil(Math.log2(9)) = 4. Row 0 is one step up.
2build1[-1, -1, 0, 0, 1, 3, 4, 1]2 steps upEach entry is prev[prev[v]]. Node 6 goes one step to 5, then one more to 4. Node 1 goes to 0, whose parent is -1, so it gets -1.
3build2[-1, -1, -1, -1, -1, 0, 1, -1]4 steps upNode 6 goes 2 steps up to 4, and row 1 says 4 goes 2 more up to 1.
4build3all -18 steps upNo node is 8 levels deep, so the whole row is -1. The row exists so that every k below 8 has a row for each of its bits.
5query 6, k = 506 to 5bit 0 is 1: jump 15 is 101 in binary, so the jumps are 1 and 4. Row 0 moves 6 to 5.
6query 6, k = 515 to 5bit 1 is 0: no jumpThe middle bit is 0, so node stays at 5.
7query 6, k = 525 to 0bit 2 is 1: jump 4up[2][5] is 0: from 5 the chain is 4, 3, 1, 0.
8query 6, k = 530 to 0bit 3 is 0: return 0The loop checks every row. All bits are used, so the answer is node 0.
9query 7, k = 407 to 7bit 0 is 04 is 100 in binary: a single jump of 4.
10query 7, k = 417 to 7bit 1 is 0Still no jump.
11query 7, k = 427 to -1jump leaves the tree: -1Node 7 has only 3 ancestors (2, 1, 0), so up[2][7] is -1 and line 16 stops early.
12query 6, k = 9--9 >= 8: return -1Line 13 rejects k before any jump: no node in an 8-node tree has 8 or more ancestors.

The 5th ancestor of 6 is 0, found with 2 jumps instead of 5 parent steps. The 4th ancestor of 7 doesn't exist, so the answer is -1, and so is the 9th ancestor of 6. The table has 4 rows of 8 entries, 32 numbers, built once and reused by every query.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Binary liftingO(log n)O(n log n)Many ancestor or common-ancestor questions on a tree that doesn't change.
Walk up the parentsO(n)O(1)One or a few questions, or a tree that changes often.
Store every ancestorO(1)O(n²)Tiny trees only: one lookup per question, but memory explodes on deep trees.
Recursive common-ancestor searchO(n)O(h)One common-ancestor question on a tree with only child pointers.

Extra memory: O(n log n): levels rows of n numbers. A million nodes need 20 rows, 20 million numbers, which matters in a browser. Typed arrays like Int32Array keep it compact.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Binary lifting and the other approaches, on a scale where each line up is 10 times more steps.
  • Binary lifting O(log n)
  • Walk up the parents, Recursive common-ancestor search O(n)
  • Store every ancestor O(1)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Binary lifting31020
Walk up the parents101,0001 million
Store every ancestor111
Recursive common-ancestor search101,0001 million

Inputs that need care

6 tricky inputs
k = 0
No bit is set, so no jump happens and the node itself is returned, which matches "0 steps up".
The root as node, with k >= 1
The first jump lands on -1, and the function returns -1 right away.
One node: parent = [-1]
levels = Math.max(1, Math.ceil(Math.log2(2))) = 1, so the table is only row 0. kthAncestor(up, 0, 0) returns 0, and any k >= 1 fails the k >= n check.
A forest, with several roots marked -1
It works as is: each tree's nodes climb to their own root and then to -1. For common-ancestor questions, first check that the two nodes have the same root.
A parent array with a cycle, like [1, 0]
That isn't a tree, and the table fills with nodes that never reach -1. The answers are meaningless and no error is thrown, so check that the input is a tree first.
A very large k, like 2 ** 40
k >> j works on 32-bit integers in JavaScript, so such a k would give the wrong bits, but line 13 rejects any k >= n before the loop.

Variations and follow-ups

Twists interviewers add

Lowest common ancestor in O(log n)

Store each node's depth. Lift the deeper node by the depth difference, then for j from the top row down, jump both nodes whenever up[j][a] !== up[j][b]. They stop just below the common ancestor, which is up[0][a].

Values along the jumps

Keep a second table beside up, such as the smallest edge weight along each jump: minUp[j][v] = Math.min(minUp[j - 1][v], minUp[j - 1][half]). A query can then report the smallest weight on the path while it jumps.

Jumping through any step function

The step doesn't have to be a tree parent. For any function f that maps a state to the next one, like "the next slide after this one", the same table answers "where am I after k steps?" in O(log k).

Sparse table

The same doubling idea on an array: min[j][i] is the smallest of the 2^j values starting at index i. A range-minimum question is then answered with two overlapping blocks.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "k-th ancestor", a tree given as a parent array, or common-ancestor questions with something like 10^5 queries.
  • Explain the doubling line in words: "4 steps up is 2 steps up, then 2 more". Then show how k = 13 becomes jumps of 8, 4, and 1.
  • State both costs: O(n log n) to build and O(log n) per query. The interviewer wants to hear that the build cost is paid once.
  • Expect "how do you get the common ancestor?". Lift the deeper node to the same depth, then jump both from the highest row down while their ancestors differ. The parent of where they stop is the answer.

Where frontend code uses it

The same idea in real UI code
  • A large org chart or file tree in an admin dashboard may need to answer many "who is this person's manager k levels up" or "which folder holds both of these" questions. Precomputing jumps keeps each answer fast.
  • Version-history tools walk back many steps through long chains of parent versions. Skip pointers that jump several versions at once are the same idea.
  • The idea of precomputing answers for power-of-two sizes also powers sparse tables, used for fast range-minimum queries over fixed data like chart values.

Related algorithms