Understanding Binary Lifting: Finding Ancestors Efficiently in Trees

Introduction

When working with trees, we sometimes need to find the ancestors of a particular node.

For example, in an organization, every employee might have a manager, and that manager might report to another manager.

Now, if we want to find an employee's manager, we can directly look at their parent in the hierarchy.

But what if we want to find the manager who is 10 levels above that employee?

We could keep moving from one parent to another until we reach the required ancestor.

This works, but if the tree is large and we need to perform thousands of such queries, repeatedly traversing the tree can become expensive.

Binary Lifting is a technique that helps us find ancestors efficiently by precomputing information that allows us to jump multiple levels at once.

Instead of moving one level at a time, we can jump 1, 2, 4, 8, 16, and more levels using powers of two.

Normal Parent Traversal vs. Binary Lifting

Let's take a tree where each node has a parent, except the root node.

        A
        |
        B
        |
        C
        |
        D
        |
        E
        |
        F
        |
        G
        |
        H

Here, A is the root node, and each node is connected to its immediate parent.

Now, we want to find the 6th ancestor of node H.

Normal Parent Traversal

We can start from H and move to its parent one level at a time.

H → G → F → E → D → C → B

We need 6 jumps to reach node B.

If we want to find the Kth ancestor of a node, this approach can take O(K) time.

For a small tree, this is fine. But if we have thousands of nodes and need to answer many ancestor queries, traversing one level at a time becomes inefficient.

Using Binary Lifting

Instead of moving to the immediate parent every time, what if we already knew the ancestor at certain distances?

For each node, we can precompute its ancestors at distances:

1, 2, 4, 8, 16, 32, ...

For example, from node H:

• 1 level above → G
• 2 levels above → F
• 4 levels above → D

Now, to find the 6th ancestor, we don't need six individual jumps.

We can split 6 into powers of two:

6 = 4 + 2

Starting from H:

H → D (4 levels) → B (2 levels)

We reached the same ancestor using just 2 jumps instead of 6.

This is the idea behind Binary Lifting.

By storing ancestors at distances that are powers of two, we can find the Kth ancestor in O(log K) time after preprocessing.

How Are These Values Calculated?

We already know that Binary Lifting stores ancestors at distances of 1, 2, 4, 8, 16, ... levels.

But how do we calculate these ancestors without moving through every parent again?

We can use the ancestor information we've already calculated.

Let's take node H from our tree.

We know:

• The 1st ancestor of H is G.
• The 2nd ancestor of H is F.

Now, we want to find the 4th ancestor of H.

Instead of moving four levels from H, we can split the journey into two jumps of 2 levels.

H → F → D

We already know that F is the 2nd ancestor of H, and D is the 2nd ancestor of F.

So, the 4th ancestor of H is the 2nd ancestor of its 2nd ancestor.

We can use the same approach for larger jumps:

• 2 levels = 1 + 1
• 4 levels = 2 + 2
• 8 levels = 4 + 4
• 16 levels = 8 + 8

Deriving the Formula

We represent the ancestor table using up[node][j], where j represents the power of two.

For example:

• up[H][0] → 2⁰ = 1 level
• up[H][1] → 2¹ = 2 levels
• up[H][2] → 2² = 4 levels

To find an ancestor (2^j) levels above a node, we divide the jump into two equal parts.

Mathematically, we want to establish:2^j = 2^(j-1) + 2^(j-1)

This means we can find an ancestor (2^j) levels above a node by making two jumps of (2^{j-1}) levels.

The first jump takes us to:

up[node][j-1]

From that ancestor, we make another jump of the same size:

up[up[node][j-1]][j-1]

So, the Binary Lifting formula becomes:

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

For example, to calculate the 4th ancestor of H:

up["H"][2] = up[up["H"][1]][1]

# 2nd ancestor of H = F
# 2nd ancestor of F = D

# Therefore, 4th ancestor of H = D

For the immediate parent, we directly store:

up[node][0] = parent[node]

If an ancestor doesn't exist, we store a special value such as -1 and avoid using it as a valid node index.

For a tree with N nodes, we generally precompute ancestors up to 2^⌊log₂ N⌋ levels.

Time and Space Complexity

For a tree with N nodes, we don't need to store every ancestor of each node.

We only store ancestors at distances of 1, 2, 4, 8, 16, ... until we reach the maximum possible depth of the tree.

For example, if our tree has 16 nodes, the jump distances we need to consider are:

1, 2, 4, 8, 16

That's just 5 entries per node, instead of storing up to 15 individual ancestors.

But how many entries do we need for a tree with N nodes?

Since our jump distances are powers of two, the maximum required power satisfies:

For a tree with N nodes, we generally precompute ancestors up to 2^⌊log₂ N⌋ levels.

2^j ≤ N

Taking logarithm base 2 on both sides:

j ≤ log₂ N

Since we start from j = 0, the maximum number of entries per node is:

⌊log₂ N⌋ + 1

Therefore, each node stores O(log N) ancestor entries.

Now, we have N nodes, and for each node, we calculate at most O(log N) entries.

So, the total number of entries is:

N × O(log N) = O(N log N)

Each entry is calculated in constant time using our previously derived formula.

Therefore:

• Time Complexity: O(N log N) — We calculate at most O(log N) ancestor entries for each of the N nodes.
• Space Complexity: O(N log N) — We store those entries in the binary lifting table.

Finding the Kth Ancestor

In our previous example, we found the 6th ancestor of node H by splitting 6 into two jumps:

6 = 4 + 2

But how do we decide which jumps to make when K is any number?

We can represent K as a sum of powers of two.

For example:

• 5 = 4 + 1
• 6 = 4 + 2
• 7 = 4 + 2 + 1
• 13 = 8 + 4 + 1

Every positive integer can be represented as a sum of distinct powers of two. This is also how numbers are represented in binary.

Using Binary Representation

Let's take K = 6.

Its binary representation is:

6 = (110)₂ = 4 + 2

Each binary digit represents a power of two:

Power of 2:    2²  2¹  2⁰
Jump size:      4   2   1
Binary digit:   1   1   0

A binary digit of 1 means we need that jump, while 0 means we can skip it.

For K = 6, we need jumps of 4 and 2 levels.

Starting from node H:

H → D → B

We reached the 6th ancestor using just two jumps.

Implementation

We can use bitwise operations to identify which jumps are required.

def kth_ancestor(node, k, up):
    bit = 0

    while k > 0 and node != -1:
        if k & 1:
            node = up[node][bit]

        k >>= 1
        bit += 1

    return node

Here:

• k & 1 checks whether the current rightmost binary digit is 1. If it is, we make the corresponding jump.
• k >>= 1 shifts K one bit to the right, allowing us to check the next binary digit.
• bit += 1 moves to the next power of two in our ancestor table.

The up table must contain the required jump columns. If K is beyond the supported range or the ancestor doesn't exist, we return -1.

Time Complexity

For every iteration, we remove one binary digit from K by shifting it right.

A positive integer K has ⌊log₂ K⌋ + 1 binary digits.

Since each iteration performs at most one table lookup, finding the Kth ancestor takes:

O(log K)

The binary lifting table is already precomputed, so we don't need to traverse the intermediate nodes individually.

Binary Lifting – Python Implementation

class BinaryLifting:
    def __init__(self, parent):
        self.n = len(parent)
        self.LOG = self.n.bit_length()

        self.up = [
            [-1] * self.LOG
            for _ in range(self.n)
        ]

        # Store immediate parents
        for node in range(self.n):
            self.up[node][0] = parent[node]

        # Precompute ancestors at powers of two
        for j in range(1, self.LOG):
            for node in range(self.n):
                prev = self.up[node][j - 1]

                if prev != -1:
                    self.up[node][j] = self.up[prev][j - 1]

    def kth_ancestor(self, node, k):
        if k < 0:
            raise ValueError("k must be non-negative")

        if k >= self.n:
            return -1

        bit = 0

        while k > 0 and node != -1:
            if k & 1:
                node = self.up[node][bit]

            k >>= 1
            bit += 1

        return node

Time and Space Complexity:

• Preprocessing: O(N log N)
• Kth Ancestor Query: O(log K)
• Space: O(N log N)

Lowest Common Ancestor (LCA)

Let's understand another use of Binary Lifting, which is finding the Lowest Common Ancestor (LCA) of two nodes in a tree.

In a tree, two nodes can have multiple common ancestors.

The Lowest Common Ancestor (LCA) is the deepest common ancestor of two nodes, meaning the common ancestor closest to both nodes.

Let's take an example:

            A
           / \
          B   C
         / \   \
        D   E   F
       / \     / \
      G   H   I   J

Here, A is the root node.

If we want to find the LCA of G and H, both nodes share D, B, and A as their ancestors.

Among them, D is the closest common ancestor.

So, LCA(G, H) = D.

Similarly:

• LCA(G, E) = B
• LCA(I, J) = F
• LCA(G, J) = A

Finding LCA Without Binary Lifting

One way to find the LCA is to move upward through the tree.

For example, to find the LCA of G and E:

• G's ancestors are D → B → A.
• E's ancestors are B → A.

The closest common ancestor is B.

We can find it by storing the ancestors of one node and checking the ancestors of the other.

This approach can take O(N) time in the worst case for a tree with N nodes.

If we have many LCA queries on a large tree, repeatedly traversing the ancestors becomes expensive.

We already have a Binary Lifting table that allows us to jump multiple levels at once. We can use the same table to find the LCA more efficiently.

Finding LCA Using Binary Lifting

We already know how Binary Lifting helps us jump multiple levels in a tree using powers of two.

We can use the same idea to find the LCA of two nodes.

There are two steps involved:

1. Bring both nodes to the same depth.
2. Move both nodes upward until we find their lowest common ancestor.

Step 1: Bring Both Nodes to the Same Depth

Let's use the same tree:

            A
           / \
          B   C
         / \   \
        D   E   F
       / \     / \
      G   H   I   J

First, we need to know the depth of each node, which is the number of edges from the root to that node.

For example:

• Depth of A = 0
• Depth of B = 1
• Depth of D = 2
• Depth of G = 3

Now, let's find the LCA of G and E.

G is at depth 3, while E is at depth 2.

Since both nodes are at different depths, we first move the deeper node upward until both are at the same depth.

The depth difference is:

3-2=1

Using our Binary Lifting table, we move G one level upward.

G → D

Now, D and E are both at depth 2.

Step 2: Move Both Nodes Upward

Once both nodes are at the same depth, we need to find where their paths meet.

Instead of moving one level at a time, we use our precomputed ancestor table to make larger jumps.

We start with the largest available jump and move toward smaller jumps.

If the ancestors of both nodes at a particular jump distance are different, we move both nodes to those ancestors.

If they're the same, we don't make that jump because it could move us to their common ancestor or above it.

For our example, D and E have the same parent, B.

So, we don't need to move them any further.

Their immediate parent is the LCA.

LCA(G, E) = B

Why Do We Check Larger Jumps First?

Our goal is to bring both nodes as close as possible to their LCA without reaching or crossing it.

For larger trees, moving through every parent would take more time.

Binary Lifting allows us to skip multiple levels whenever the ancestors of both nodes are different.

After checking all the powers of two, both nodes will be immediately below their LCA.

We can then return the parent of either node.

One special case: If both nodes become the same after adjusting their depths, that node itself is the LCA.

Since we only check O(log N) jump distances, finding the LCA takes O(log N) time after preprocessing.

Binary Lifting Implementation for LCA

We can extend our existing Binary Lifting implementation to find the Lowest Common Ancestor of two nodes.

Along with the ancestor table, we also need to store the depth of each node.

class BinaryLiftingLCA:
    def __init__(self, n, edges, root=0):
        self.n = n
        self.LOG = n.bit_length()
        self.depth = [0] * n
        self.up = [[-1] * self.LOG for _ in range(n)]

        # Build adjacency list
        graph = [[] for _ in range(n)]
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        # Find parents and depths
        parent = [-1] * n
        visited = [False] * n
        visited[root] = True
        stack = [root]

        while stack:
            node = stack.pop()
            self.up[node][0] = parent[node]

            for neighbor in graph[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    parent[neighbor] = node
                    self.depth[neighbor] = self.depth[node] + 1
                    stack.append(neighbor)

        # Precompute ancestors at powers of two
        for j in range(1, self.LOG):
            for node in range(n):
                prev = self.up[node][j - 1]

                if prev != -1:
                    self.up[node][j] = self.up[prev][j - 1]

    def kth_ancestor(self, node, k):
        if k < 0:
            raise ValueError("k must be non-negative")

        if k > self.depth[node]:
            return -1

        bit = 0

        while k > 0:
            if k & 1:
                node = self.up[node][bit]

            k >>= 1
            bit += 1

        return node

    def lca(self, u, v):
        # Step 1: Identify the deeper node
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        # Step 2: Calculate the depth difference
        depth_diff = self.depth[u] - self.depth[v]

        # Step 3: Bring both nodes to the same depth
        u = self.kth_ancestor(u, depth_diff)

        if u == v:
            return u

        # Step 4: Move both nodes upward
        for j in range(self.LOG - 1, -1, -1):
            if (self.up[u][j] != -1
                    and self.up[u][j] != self.up[v][j]):
                u = self.up[u][j]
                v = self.up[v][j]

        # Step 5: Return their common parent
        return self.up[u][0]

The lca() method follows these steps:

Step 1: Identify the deeper node

We compare the depths of both nodes and make sure u is the deeper node.

Step 2: Calculate the depth difference

depth_diff = self.depth[u] - self.depth[v]

This tells us how many levels the deeper node needs to move upward.

For example, if u is at depth 5 and v is at depth 2:

depth_diff = 5 - 2 = 3

So, we need to move u upward by 3 levels.

Step 3: Bring both nodes to the same depth

We use our previously implemented kth_ancestor() method to move the deeper node upward by depth_diff levels.

If both nodes become the same, that node itself is the LCA.

Step 4: Move both nodes upward

We check their ancestors from the largest jump to the smallest. Whenever their ancestors are different, we move both nodes upward.

After completing these jumps, both nodes are immediately below their LCA.

We return the immediate parent of either node.

Note: This code uses the kth_ancestor() method from our previous implementation. We need to include that method in the class when running the code, but we're not repeating it here.

The implementation assumes a valid, connected, undirected tree with nodes numbered from 0 to N-1.

Time and Space Complexity

• Preprocessing: O(N log N) — Building the ancestor table.
• LCA Query: O(log N) — Finding the depth difference and checking the precomputed jump distances.
• Space: O(N log N) — Storing the ancestor table and node depths.

The same precomputed table can be reused for multiple LCA queries.

Practice Problems

Here are a few LeetCode problems to practice Binary Lifting:

1. Kth Ancestor of a Tree Node — LeetCode
2. Lowest Common Ancestor of a Binary Tree — LeetCode
3. Number of Ways to Assign Edge Weights II — LeetCode