Binary Lifting for LCA and Kth Ancestor Queries

---

The Problem: Ancestor Queries on Trees

Given a rooted tree with n nodes, we want to answer two types of queries efficiently:

1. Kth Ancestor: Given a node v and integer k, find the ancestor of v that is exactly k edges above it.
2. Lowest Common Ancestor (LCA): Given two nodes u and v, find their deepest common ancestor.

The naive approach walks up the tree one step at a time, which is O(n) per query in the worst case (a long chain). With Q queries, this becomes O(n * Q).

Binary lifting reduces each query to O(log n) by precomputing “jump pointers” — for each node, we store its ancestor at distance 1, 2, 4, 8, 16, and so on.

---

The Key Idea: Powers-of-2 Jumps

Just like a number can be decomposed into powers of 2 (binary representation), any distance k can be reached by combining jumps of powers of 2.

For example, to go 13 steps up: 13 = 8 + 4 + 1, so we jump 8, then 4, then 1.

We store a table up[k][v] where:

• up[0][v] = parent of v (1 step up)
• up[1][v] = grandparent of v (2 steps up)
• up[2][v] = 4th ancestor (4 steps up)
• In general: up[k][v] = up[k-1][up[k-1][v]] (jump 2^(k-1) from the node that is already 2^(k-1) above v)

---

Building the Jump Table

Preprocessing with DFS

import math
from collections import defaultdict, deque

class BinaryLifting:
    """Binary lifting for LCA and kth ancestor queries."""
    
    def __init__(self, n, edges, root=0):
        """
        n: number of nodes (0-indexed)
        edges: list of (u, v) undirected edges
        root: root of the tree
        """
        self.n = n
        self.root = root
        self.LOG = max(1, int(math.log2(n)) + 1) if n > 1 else 1
        
        # Build adjacency list
        self.adj = defaultdict(list)
        for u, v in edges:
            self.adj[u].append(v)
            self.adj[v].append(u)
        
        # up[k][v] = 2^k-th ancestor of v (-1 if doesn't exist)
        self.up = [[-1] * n for _ in range(self.LOG)]
        self.depth = [0] * n
        
        # BFS to set up parents and depths
        self._bfs_preprocess()
        
        # Fill remaining levels of the jump table
        self._build_table()
    
    def _bfs_preprocess(self):
        """Set up parent (up[0]) and depth using BFS from root."""
        visited = [False] * self.n
        queue = deque([self.root])
        visited[self.root] = True
        self.up[0][self.root] = self.root  # Root's parent is itself
        self.depth[self.root] = 0
        
        while queue:
            node = queue.popleft()
            for neighbor in self.adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    self.up[0][neighbor] = node
                    self.depth[neighbor] = self.depth[node] + 1
                    queue.append(neighbor)
    
    def _build_table(self):
        """Fill the jump table using DP: up[k][v] = up[k-1][up[k-1][v]]."""
        for k in range(1, self.LOG):
            for v in range(self.n):
                mid = self.up[k - 1][v]
                if mid != -1:
                    self.up[k][v] = self.up[k - 1][mid]
                else:
                    self.up[k][v] = -1
    
    def kth_ancestor(self, v, k):
        """Return the kth ancestor of node v, or -1 if it doesn't exist."""
        if k > self.depth[v]:
            return -1
        
        current = v
        for bit in range(self.LOG):
            if k & (1 << bit):
                current = self.up[bit][current]
                if current == -1:
                    return -1
        
        return current
    
    def lca(self, u, v):
        """Return the Lowest Common Ancestor of nodes u and v."""
        # Step 1: Bring both nodes to the same depth
        if self.depth[u] < self.depth[v]:
            u, v = v, u  # Ensure u is deeper
        
        diff = self.depth[u] - self.depth[v]
        u = self.kth_ancestor(u, diff)
        
        # Step 2: If they're the same node, we found the LCA
        if u == v:
            return u
        
        # Step 3: Jump both nodes up together
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                u = self.up[k][u]
                v = self.up[k][v]
        
        # Now u and v are children of the LCA
        return self.up[0][u]
    
    def distance(self, u, v):
        """Return the number of edges between u and v."""
        ancestor = self.lca(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[ancestor]

Example Usage

# Build a tree:
#         0
#        / \
#       1   2
#      / \    \
#     3   4    5
#    / \   \
#   6   7   8

n = 9
edges = [
    (0, 1), (0, 2),
    (1, 3), (1, 4),
    (2, 5),
    (3, 6), (3, 7),
    (4, 8)
]

bl = BinaryLifting(n, edges, root=0)

# Kth ancestor queries
print(f"2nd ancestor of 7: {bl.kth_ancestor(7, 2)}")  # 1
print(f"3rd ancestor of 7: {bl.kth_ancestor(7, 3)}")  # 0
print(f"1st ancestor of 8: {bl.kth_ancestor(8, 1)}")  # 4

# LCA queries
print(f"LCA(6, 8) = {bl.lca(6, 8)}")    # 1
print(f"LCA(7, 5) = {bl.lca(7, 5)}")    # 0
print(f"LCA(6, 7) = {bl.lca(6, 7)}")    # 3
print(f"LCA(3, 4) = {bl.lca(3, 4)}")    # 1

# Distance queries
print(f"dist(6, 8) = {bl.distance(6, 8)}")  # 4
print(f"dist(7, 5) = {bl.distance(7, 5)}")  # 5

Output:

2nd ancestor of 7: 1
3rd ancestor of 7: 0
1st ancestor of 8: 4
LCA(6, 8) = 1
LCA(7, 5) = 0
LCA(6, 7) = 3
LCA(3, 4) = 1
dist(6, 8) = 4
dist(7, 5) = 5

---

Understanding the LCA Algorithm

Step 1: Equalize Depths

If u is deeper than v, we jump u up by depth[u] - depth[v] steps using kth_ancestor. This uses binary decomposition of the difference.

Step 2: Check if Same Node

If after equalizing, u == v, then the original deeper node was a descendant of the shallower one, and the LCA is v.

Step 3: Binary Jump Together

We iterate from the highest power of 2 down to 0. At each level k:

• If up[k][u] != up[k][v], we know the LCA is above this level, so we jump both up.
• If up[k][u] == up[k][v], the LCA might be at this level or below, so we do not jump (to avoid overshooting).

After all levels, u and v will be direct children of the LCA. So up[0][u] is the answer.

---

Binary Lifting with Edge Weights

A common extension: find the minimum/maximum edge weight on the path between two nodes.

class BinaryLiftingWeighted:
    """Binary lifting with path min/max queries."""
    
    def __init__(self, n, weighted_edges, root=0):
        """weighted_edges: list of (u, v, weight)."""
        self.n = n
        self.root = root
        self.LOG = max(1, int(math.log2(n)) + 1) if n > 1 else 1
        
        self.adj = defaultdict(list)
        for u, v, w in weighted_edges:
            self.adj[u].append((v, w))
            self.adj[v].append((u, w))
        
        self.up = [[-1] * n for _ in range(self.LOG)]
        self.depth = [0] * n
        # max_edge[k][v] = max edge weight on path from v to up[k][v]
        self.max_edge = [[0] * n for _ in range(self.LOG)]
        
        self._bfs_preprocess()
        self._build_table()
    
    def _bfs_preprocess(self):
        visited = [False] * self.n
        queue = deque([self.root])
        visited[self.root] = True
        self.up[0][self.root] = self.root
        
        while queue:
            node = queue.popleft()
            for neighbor, weight in self.adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    self.up[0][neighbor] = node
                    self.depth[neighbor] = self.depth[node] + 1
                    self.max_edge[0][neighbor] = weight
                    queue.append(neighbor)
    
    def _build_table(self):
        for k in range(1, self.LOG):
            for v in range(self.n):
                mid = self.up[k - 1][v]
                if mid != -1:
                    self.up[k][v] = self.up[k - 1][mid]
                    self.max_edge[k][v] = max(
                        self.max_edge[k - 1][v],
                        self.max_edge[k - 1][mid]
                    )
    
    def path_max(self, u, v):
        """Return max edge weight on path from u to v."""
        result = 0
        
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        
        diff = self.depth[u] - self.depth[v]
        for k in range(self.LOG):
            if diff & (1 << k):
                result = max(result, self.max_edge[k][u])
                u = self.up[k][u]
        
        if u == v:
            return result
        
        for k in range(self.LOG - 1, -1, -1):
            if self.up[k][u] != self.up[k][v]:
                result = max(result, self.max_edge[k][u], self.max_edge[k][v])
                u = self.up[k][u]
                v = self.up[k][v]
        
        result = max(result, self.max_edge[0][u], self.max_edge[0][v])
        return result


# Example
edges = [(0, 1, 3), (0, 2, 7), (1, 3, 1), (1, 4, 5), (2, 5, 2)]
blw = BinaryLiftingWeighted(6, edges, root=0)
print(f"Max edge on path 3->5: {blw.path_max(3, 5)}")  # 7
print(f"Max edge on path 3->4: {blw.path_max(3, 4)}")  # 5

---

Binary Lifting on Functional Graphs

Binary lifting is not limited to trees. It works on any functional graph (where each node has exactly one outgoing edge). A classic example: “starting at node v, where are you after k steps?”

def build_functional_graph_lifting(next_node, n, max_k):
    """
    next_node[v] = the node you go to from v (one outgoing edge per node).
    Returns table where table[k][v] = node reached after 2^k steps from v.
    """
    LOG = max_k
    table = [[0] * n for _ in range(LOG)]
    
    # Level 0: one step
    for v in range(n):
        table[0][v] = next_node[v]
    
    # Fill remaining levels
    for k in range(1, LOG):
        for v in range(n):
            table[k][v] = table[k - 1][table[k - 1][v]]
    
    return table

def query_k_steps(table, v, k):
    """Return the node reached after exactly k steps from v."""
    current = v
    for bit in range(len(table)):
        if k & (1 << bit):
            current = table[bit][current]
    return current


# Example: circular graph 0->1->2->3->4->0
next_node = [1, 2, 3, 4, 0]
table = build_functional_graph_lifting(next_node, 5, 20)

print(f"Start at 0, after 7 steps: {query_k_steps(table, 0, 7)}")   # 2
print(f"Start at 0, after 13 steps: {query_k_steps(table, 0, 13)}")  # 3
print(f"Start at 2, after 1000000 steps: {query_k_steps(table, 2, 1000000)}")  # 2

---

Complexity Analysis

Operation	Time	Space
Preprocessing	O(n log n)	O(n log n)
Kth Ancestor	O(log n)	-
LCA	O(log n)	-
Distance	O(log n)	-
Path min/max	O(log n)	O(n log n) extra

Comparison with Other LCA Methods

Method	Preprocessing	Query	Space
Naive (walk up)	O(n)	O(n)	O(n)
Binary Lifting	O(n log n)	O(log n)	O(n log n)
Euler Tour + Sparse Table	O(n log n)	O(1)	O(n log n)
Euler Tour + Segment Tree	O(n)	O(log n)	O(n)
Tarjan’s Offline LCA	O(n * alpha(n))	O(1) offline	O(n)

Binary lifting is often the best choice because:

• It is simpler to implement than Euler tour + sparse table.
• It naturally supports kth ancestor and path queries.
• O(log n) per query is fast enough for most problems (up to 10^5 queries on 10^5 nodes).

---

Applications

1. Path Queries on Trees

Find the sum/min/max of values on the path between two nodes:

1. Find LCA using binary lifting.
2. Aggregate values from u up to LCA and from v up to LCA.

2. Level Ancestor Problem

“Find the ancestor of node v at depth d” is equivalent to kth_ancestor(v, depth[v] - d).

3. Tree Isomorphism

Binary lifting helps compute hash values for subtree comparisons.

4. Planet Queries (CSES)

Classic functional graph problem: “Start at planet x, where are you after k teleportations?”

---

Practice Problems

1. Company Queries I (CSES) — Direct kth ancestor query using binary lifting.
2. Company Queries II (CSES) — LCA query using binary lifting.
3. Distance Queries (CSES) — Find distance between two nodes using LCA.
4. Planet Queries I (CSES) — Functional graph, kth step query.
5. Maximum Edge on Path — Binary lifting with path max aggregation.
6. Weighted LCA — Find the sum of edge weights on the path between two nodes.

---

Key Takeaways

• Binary lifting precomputes ancestors at powers of 2, enabling O(log n) jumps to any ancestor.
• The recurrence up[k][v] = up[k-1][up[k-1][v]] is the core of the technique.
• LCA queries work by equalizing depths, then jumping both nodes up together while avoiding overshooting.
• The technique extends naturally to weighted paths, functional graphs, and path aggregation queries.
• With O(n log n) preprocessing and O(log n) queries, binary lifting is the most practical LCA solution for competitive programming.