Binary Lifting and Its Applicationsby@infinity
642 reads

Binary Lifting and Its Applications

tldt arrow
Read on Terminal Reader
Read this story w/o Javascript

Too Long; Didn't Read

The tree data structure is one of the most fascinating data structures in computer science. Since k can be at most n, we can always represent k as the sum of log(n) elements. According to the ideas discussed in the motivation section, we will need to store (2^x)th ancestor for each node. 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 The below code assumes that the tree consists of n nodes from 0 to n-1. However, the catch in this algorithm is that we can use Binary Lifting to speed up steps 2 and 4. Consider that the node pointer n1 points to the node at a larger depth, if not swap n1 and n2.

Companies Mentioned

Mention Thumbnail
Mention Thumbnail
featured image - Binary Lifting and Its Applications
Rishabh Agarwal HackerNoon profile picture


Rishabh Agarwal

Tech Enthusiast!

Receive Stories from @infinity

react to story with heart


. . . comments & more!