Binary Lifting(Jump pointers)

The generic problem it solves:-

There is a tree of size N, rooted at 0. Answer Q queries: Given v and k, find k-th ancestor of v.

Ancestor means parent levels

To represent for example 19th ancestor it will need to go 19 levels up from vertex v . Normally if we go manually it might take O(N) time complexity and total of O(N*N) time complexity. To reduce this what we can do it is represent 19 in binary(sum of powers of 2) 19=10011=16+2+1

which are jumps taken to shortest time complexity to O(logn) as power of 2 jump we are taking.

To achieve this we use Preprocessing:

int up[N][LOG] up[v][j] — 2^j-th ancestor of v for v = 0 .. N-1: up[v] [0] = parent[v] up[v][1]= up[up[v][0]][0] up[v][2] = up[up[v] [1]][1] up[v][3]= up[up[v][2]][2]

Now generalizing up[v][j]=up[up[v][j−1]][j−1]

Key Idea

The core idea is that a jump of size 2j can be broken into two smaller jumps of size 2^(j−1) . Why? Because:

2^j=2^(j−1)+2^(j−1)

This means that to reach the 2j -th ancestor of v , you can:

1. First jump 2j−1 levels up from v to some intermediate node x .
2. Then, from x , jump another 2j−1 levels up.

Since both jumps are of size 2j−1 , and we’ve already precomputed all 2j−1 -th ancestors during the preprocessing phase, this allows us to efficiently compute the 2j -th ancestor.

Note: parent[i] < i//if this condition is valid then only the binary lifting will work

Pseudocode:

int up[N][LOG]//LOG is depth up[v][j] — 2^j-th ancestor of v for v = 0 .. N-1: up[v] [0] = parent[v] for j = 1 .. LOG-1:for v = 0 .. N-1: up[v][j] = up[ up[v][j-1] ][j-1]// precomputing each levelwise.

Time&Space complexity

O(N*log(N))

Sample python code to find Kth common Ancestor using Binary Lifting: from typing import List

from math import log2

class TreeAncestor:

def init(self, n: int, parent: List[int]):

self.max_depth = int(log2(n)) + 1

self.ancestortable = [[-1 for in range(self.maxdepth)] for in range(n)]

for node in range(n):

self.ancestor_table[node][0] = parent[node]

for level in range(1, self.max_depth):

for node in range(n):

if self.ancestor_table[node][level — 1] != -1:

self.ancestor_table[node][level] = self.ancestor_table[

self.ancestor_table[node][level — 1]

][level — 1]

def getKthAncestor(self, node: int, k: int) -> int:

for level in range(self.max_depth):

mask = 1 << level

if k & mask:

node = self.ancestor_table[node][level]

if node == -1:

return -1

return node