Pattern 3: Binary Lifting, Kth Ancestor Node Intuition

There is a very good problem with leetcode which cover this concept.

Leetcode: https://leetcode.com/problems/kth-ancestor-of-a-tree-node/

Problem: You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of ith node. The root of the tree is a node 0. Find the kth the ancestor of a given node.

The kth The ancestor of a tree node is the kth node in the path from that node to the root node.

Implement the TreeAncestor class:

• TreeAncestor(int n, int[] parent)initializes the object with the number of nodes in the tree and the parent array.
• int getKthAncestor(int node, int k) Return the kth ancestor of the given node node. If there is no such ancestor, return -1.

Example 1:

Input
["TreeAncestor", "getKthAncestor", "getKthAncestor", "getKthAncestor"]
[[7, [-1, 0, 0, 1, 1, 2, 2]], [3, 1], [5, 2], [6, 3]]
Output
[null, 1, 0, -1]

Intuition: The first solution which came to our mind is to just traverse to their kth parent and return it but here the complexity is O(n) in the worse case as three can be total left or right skew.

So how can we optimize it, here is the binary lifting that comes into the picture.

The idea behind the Binary Lifting is to play with the power of 2.

What does it even mean? Let's think what if somehow we are able to jump in the power of 2 ?As we know any number can be represented in the power of 2 , like 19 = 16+ 2 +1 , 20 = 16+ 4 , 6 = 2+ 4 etc. (remember distinct number only)

So if we are standing to any node x, what if we jump to its kth ancestor like this, But wait, how to jump here :) Now that preprocessing comes here, we can store the parent of any node in the power of 2.

For example : For node x-> [ 1st parent , 2nd parent , 4th parent , 8th parent ..so on ], For all node

We can store it like this for all the nodes in the tree and at the time of query, let's suppose for node = 4 and k = 2 , so we can jump directly to 0, as k = 2 ( which is an exact power of 2)

How to precompute:

We can take 2d array of size(n x LOG), here LOG = highest power of 2 which is smaller than n, Why LOG? because the maximum jump is no more than LOG(N)?

 int log = log2(n);
 vector<vector<int>>par(n,vector<int>(log));
      //storing first parent as itself.
        for (int i = 0; i < n; i++) par[i][0] = parent[i];
              
           for (int j = 1; j < log; j++) {
            for (int i = 0; i < n; i++) {
                  //if parent out of bound (in case) 
                if (par[i][j - 1] == -1) par[i][j] = -1;


               
     //general formula 
     // how can i store 8 in 2nd parent of 10?
    // I CAN TAKE from par[par[i][j-1]] which is 9, and 8 is first parent of 9
       
          // par[i][j]= par[par[i][j-1]] [ j-1] 
               else par[i][j] = par[par[i][j - 1]][j - 1];
            }
        }

Answering Query :

Suppose node = 10 and k = 5, we can jump like 4 + 1
We can traverse to all the 1 bit in the K , which represent power of 
2 jumps actually isn't?
Like 5= 101= > 1* 2^2 + 0* 2^0 + 1*2^0 = 5

Main logic:
  1.  10 to 4
  2.  4 to 1

The answer is the last node we reached like this.

  int getKthAncestor(int node, int k) {
      
   
      for(int i=0;i<log;i++){

//We can traverse to all the 1 bit in the K , which represent power of 
//2 jumps actually isn't?
//here we doing the same thing

          if(((k>>i)&1)==1){
          //move to that parent
              node=ar[node][i];
              if(node==-1)return -1;
        }

      }
      return node;  
        
    }

Thats it! Here is the complexity change from O(n) to O( Log n) using precomputing.

Interesting question based on Binary lifting: https://leetcode.com/contest/weekly-contest-361/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/