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.