8.8 Binary Lifting

Many tree algorithms repeatedly ask the same question:

What is the ancestor of this node k levels above?

At first glance, the problem seems trivial. Follow the parent pointer k times and stop. Unfortunately, this approach becomes expensive when trees are large or when millions of queries must be processed.

Binary Lifting transforms repeated ancestor traversal into a logarithmic-time operation. It is one of the most important preprocessing techniques for trees and serves as the foundation for efficient Lowest Common Ancestor queries, distance calculations, path queries, and numerous competitive programming problems.

The core idea resembles binary search. Instead of moving upward one edge at a time, move upward in powers of two.

Problem

You need to answer ancestor queries efficiently.

Given:

node = u
distance = k

find:

the k-th ancestor of u

without traversing one edge at a time.

Solution

Precompute ancestors at powers of two.

For every node:

up[node][0]

stores the parent.

up[node][1]

stores the grandparent.

up[node][2]

stores the fourth ancestor.

up[node][3]

stores the eighth ancestor.

In general:

up[node][j]

stores the:

2^j-th ancestor

of the node.

Consider this tree:

0
|
1
|
2
|
3
|
4
|
5
|
6

The ancestor table for node 6 looks like:

Power	Ancestor
2⁰ = 1	5
2¹ = 2	4
2² = 4	2
2³ = 8	none

Once this table exists, large jumps become possible.

Building the Parent Array

Binary Lifting begins with a DFS.

package main

func buildParents(
    tree [][]int,
    node int,
    parent int,
    depth int,
    parents []int,
    depths []int,
) {
    parents[node] = parent
    depths[node] = depth

    for _, child := range tree[node] {
        buildParents(
            tree,
            child,
            node,
            depth+1,
            parents,
            depths,
        )
    }
}

This computes:

parent of every node
depth of every node

Both are needed later.

Constructing the Lifting Table

Suppose:

n = 100000

The largest useful power of two is:

log₂(n)

which is approximately:

To be safe, many implementations allocate around:

const LOG = 20

Create the table:

up := make([][]int, n)

for i := range up {
    up[i] = make([]int, LOG)
}

Fill the first column:

for node := 0; node < n; node++ {
    up[node][0] = parent[node]
}

Build larger jumps:

for j := 1; j < LOG; j++ {
    for node := 0; node < n; node++ {
        ancestor := up[node][j-1]

        if ancestor == -1 {
            up[node][j] = -1
            continue
        }

        up[node][j] = up[ancestor][j-1]
    }
}

The recurrence is:

2^j ancestor =
2^(j-1) ancestor
of
2^(j-1) ancestor

This construction is the heart of Binary Lifting.

Finding the k-th Ancestor

Suppose we need the:

13th ancestor

of a node.

Write:

13 = 8 + 4 + 1

Binary representation:

1101₂

Therefore:

jump 8 levels
jump 4 levels
jump 1 level

Implementation:

func kthAncestor(
    node int,
    k int,
    up [][]int,
) int {
    bit := 0

    for k > 0 {
        if k&1 == 1 {
            node = up[node][bit]

            if node == -1 {
                return -1
            }
        }

        k >>= 1
        bit++
    }

    return node
}

The number of jumps is proportional to the number of bits.

Complexity:

O(log k)

instead of:

O(k)

Example Walkthrough

Consider:

0
|
1
|
2
|
3
|
4
|
5
|
6

Find:

6th ancestor of node 6

Binary form:

6 = 4 + 2

The algorithm performs:

jump 4 levels
jump 2 levels

Result:

Only two table lookups are required.

A naive approach would perform six parent traversals.

Using Binary Lifting for LCA

The main reason Binary Lifting became popular is that it accelerates Lowest Common Ancestor queries.

The process:

Equalize depths.
Jump upward using powers of two.
Find the highest level where ancestors differ.
Return the parent.

Because jumps occur in powers of two, the search resembles binary search on ancestor chains.

The resulting complexity becomes:

O(log n)

per query.

Without Binary Lifting:

O(n)

in the worst case.

For large trees, the difference is dramatic.

Jumping While a Condition Holds

Binary Lifting is not limited to ancestor queries.

Suppose each node stores some property.

color
weight
timestamp

Instead of asking:

What is the k-th ancestor?

you may ask:

What is the highest ancestor
whose value satisfies a condition?

The algorithm starts with large jumps and gradually refines them.

This pattern appears in:

path constraints
hierarchy queries
version-control systems
genealogy systems
permission trees

Binary Lifting provides the infrastructure.

The query logic changes.

Space-Time Tradeoff

Binary Lifting accelerates queries by storing extra information.

For:

n nodes

and:

LOG levels

memory usage is:

O(n log n)

The tradeoff is intentional.

Method	Query	Memory
Parent walking	O(n)	O(n)
Binary Lifting	O(log n)	O(n log n)

For small trees, parent walking may be sufficient.

For thousands or millions of queries, Binary Lifting usually wins.

Visualizing the Table

Imagine the ancestor table as a collection of shortcuts.

Instead of:

6
|
5
|
4
|
3
|
2
|
1
|
0

we create additional edges:

6 --------> 2
 \          ^
  \         |
   ------> 4

These shortcuts allow the algorithm to leap over large portions of the tree.

The concept is similar to:

skip lists
sparse tables
doubling algorithms
exponentiation by squaring

All of them trade preprocessing for faster queries.

Complexity Analysis

Let:

n = number of nodes
LOG = ⌈log₂(n)⌉

Preprocessing:

Operation	Complexity
DFS depths	O(n)
Build table	O(n log n)
Total preprocessing	O(n log n)

Queries:

Operation	Complexity
k-th ancestor	O(log n)
LCA	O(log n)
Distance query (with LCA)	O(log n)

Memory:

Structure	Complexity
Ancestor table	O(n log n)

Common Mistakes

A common mistake is allocating too few columns.

If:

LOG = 10

but the tree depth exceeds:

2^10

some ancestor queries become impossible.

Another mistake is forgetting to initialize root ancestors.

The root has no parent.

parent[root] = -1

Every jump above the root should remain:

-1

A third mistake is confusing:

2^j

with:

The table stores exponential jumps, not linear jumps.

The recurrence only works because each level doubles the jump distance.

Takeaway

Binary Lifting converts repeated ancestor traversal into a logarithmic-time operation. By precomputing ancestors at powers of two, the algorithm can jump through the tree in large steps rather than following parent pointers one edge at a time. This preprocessing technique forms the basis of efficient Lowest Common Ancestor queries and many advanced path algorithms. More broadly, Binary Lifting demonstrates a recurring algorithmic theme: spend additional memory and preprocessing time to dramatically accelerate future queries.