Binary Lifting and Its Applications

The tree data structure is one of the most fascinating data structures in computer science. Many interesting problems can be framed based on this data structure. Today we will be discussing one such interesting problem. Here is how the problem can be defined - Given a rooted tree with n nodes, you have to answer q queries. In each query you have to find the k^th ancestor of a node. Let us first discuss a simple solution. For each query, we iterate over all the ancestors of the given node. We return the required ancestor node. Here is a pseudo implementation. def solveQuery(node, k): while k>0: k--; node = parent[node]; return node; Though the implementation is simple, the worst-case time complexity is . Thus the solution won’t work when quadratic implementation is too costly. This is where comes into the picture. It is an interesting idea of solving the same problem in . O(N.Q) Binary Lifting O(log(N).Q) Motivation for Binary Lifting With our failed attempt in solving the problem efficiently, we can feel the need for some pre-processing. The pre-processing that we perform should help us answer each query quickly. The big question is, what kind of pre-processing does the problem need? Pre-processing is the process of performing (some) computation beforehand to support the handling of each query in a better and more efficient manner. Some meta-data is maintained as a part of this process, which is used when answering actual queries. Let us think about it. We currently know for each node its parent. So from any node, we can only find ancestor of a node in constant time. So when we are faced with the problem of finding the ancestor we are forced to take at least hops. In other words, we are representing as , where appears times. So, what if we can find any parent of a node in constant time? We can certainly represent as the sum of the powers of . Since can be at most , we can always represent as the sum of elements. Thus answering each query now takes time. 1^st k^th k k 1 + 1 + … + 1 1 k (2^x)th k 2 k n k log(n) O(log(n)) Thus, if we can perform the preprocessing efficiently, the overall time complexity becomes . O(PP + Q.log(N)) Actual Algorithm for Binary Lifting The complete process of Binary Lifting is divided into two parts - (1) Pre-Processing and (2) Query Resolution. We will be discussing these in the following sub-sections. Pre-Processing According to the ideas discussed in the motivation section, we will need to store ancestor for each node. Let us store this information in a table . The dimensions of this table are . Here is what each entry in this table represents - (2^x)th ancestor n*log(n) ancestor[n][x] -> (2^x)th parent of node n Note that since the first ancestor of any node is its own parent we can write for each node . Now to fill the remaining entries we can follow the following recursive relation - ancestor[n][0] = parent[n] n ancestor[n][x] = ancestor[ancestor[n][x-1]][x-1] The idea with which we can arrive upon the above relation is as follows - To reach the ancestor we can make two jumps of size . Since , we will ultimately reach the required ancestor. Thus we have all the required knowledge for performing the pre-processing step. Here is a pseudo implementation. (2^x)th (2^(x-1)) (2^(x-1)) + (2^(x-1)) = (2^(x)) for node in [0:n-1]: ancestor[node][0] = parent[node] // We can not go up from root for x in [1:log(n)]: ancestor[root][x] = root for x in [1:log(n)]: for node in [0:n-1]: if node is root then continue ancestor[node][x] = ancestor[ancestor[node][x-1]][x-1] Query Resolution Once we have completed the pre-processing part, we can answer each query efficiently. The idea is the same as that discussed in the motivation section, we will express k as the sum of powers of 2. We will then move up the tree following these powers of 2. The pseudo-code below expresses this idea more succinctly. def solveQuery(node, k): for i in [31:0]: if k & (1 0: // Checking if 2^i is present in binary representation of k node = ancestor[node][i] // Move up to (2^i)th ancestor return node Implementation for Binary Lifting The below code assumes that the tree consists of n nodes from 0 to n-1. Since a tree with n nodes has n-1 edges, the input provides these n-1 edges in parent to child format. The tree is rooted at 0. #include using namespace std; vector parent; vector > ancestor; int main() { int n; cin>>n; // n is the number of nodes numbered 0 to n-1 int LOG = log2(n); parent.assign(n, 0); ancestor.assign(n, vector (LOG+2)); // Assuming node 0 is the root of the tree parent[0] = 0; // Assuming next n-1 lines contain edges in format: parent_node child_node for(int i=0; i >p>>c; parent[c] = p; } for(int i=0; i >q; // Number of Queries while(q--) { int node, k; cin>>node>>k; for(int i=LOG+1; i>=0; i--) { if( k & (1<<i) ) node = ancestor[node][i]; } cout<<node<<endl; } } Lowest Common Ancestor (LCA) - Application of Binary Lifting Having understood the interesting ideas of Binary Lifting, we can focus our attention on some of its interesting applications. One such application is to find the of a given pair of nodes in a tree. Also, assume that there can be queries of such kinds. Surprisingly we can use the process of Binary Lifting to solve this task quite elegantly. lowest common ancestor Q We begin with a description of the algorithm. We will then see where Binary Lifting comes into play. We are given two nodes and say n1 and n2 are pointers to these nodes. We have to find their LCA. Move up the pointer pointing to the node at a larger depth (farthest from the root) until the depth of both the nodes become equal. If both n1 and n2 point to the same node, the node being pointed is the LCA. We return this node and terminate. Else, we move to step 4. We advance both node pointers up the tree until they can no longer be moved without pointing to the same node. Return the parent of the node pointed by n1 as the LCA. The algorithm is fairly simple and a naive implementation will take O(n) time to return the LCA. However, the catch in this algorithm is that we can use Binary Lifting to speed up steps 2 and 4. We first see how it fits in step 2. Consider that the node pointer points to the node at a larger depth, if not swap and . Now according to step 2, we need to move the node pointer up until the depth of the newly pointed node becomes equal to that of the node pointed by . We can see this as finding ancestor of the node pointed to by . This is solvable in logarithmic time using Binary Lifting. n1 n1 n2 n1 n2 [depth(n1)-depth(n2)]th n1 Now on to step 4. At the point of reaching step 4, we are certain that nodes pointed by and are different. We have to move up both the node pointers simultaneously while ensuring they do not point to the same node. The following code snippet describes how we can use binary lifting to perform this step. n1 n2 n1, n2 =0; i--) { if(ancestor[n1][i]!=ancestor[n2][i]) { n1 = ancestor[n1][i]; n2 = ancestor[n2][i]; } } return parent[n1] as LCA Concluding Remarks This completes this amazing process of Binary Lifting. It is often fascinating how simple ideas can be used to solve problems of great difficulty. We discussed one of the many applications of Binary Lifting i.e., Lowest Common Ancestor(LCA). Can you figure out any others? Do let me know in the comment section😊. You can follow me on Twitter at . Stay tuned for more interesting articles. @rrriiisss03

Binary Lifting and Its Applications

Too Long; Didn't Read

Companies Mentioned

@infinity

RELATED STORIES