Level ancestor problem

In graph theory, the Level Ancestor Problem is the problem of preprocessing a given rooted tree T in order to answer Level Ancestor Queries. Let T be a rooted tree and let v be a node of T, the level ancestor query LA(v,d) requests the depth d ancestor of node v. The depth of a node v in a tree is the number of edges on the shortest path from the root of the tree to node v.

Level Ancestor Query

Level Ancestor of (v,2) and the path from root r to the node v.

One of the fundamental algorithmic problems on trees is to find level ancestors of nodes. The simplest way to find a level ancestor of a node is to climb up the tree towards the root of the tree. On the path to the root of the tree, every ancestor of a node can be visited and therefore reported. In this case, the tree does not need to be preprocessed and the time to answer a query is O(n). This approach is not feasible in situations where a large number of a queries are required to be processed. Alternatively, all the possible solutions can be precomputed and stored in a table. In this case, the queries can be answered in O(1) but the space and the preprocessing time is O(n²). However, a tree can be preprocessed in O(n) such that every Level Ancestor Query can be answered in O(1). There is a number of known algorithms that can optimally pre-process a given tree and answer such queries in constant time. The simplest queries that can be answered in constant time without any preprocessing are LA(v, 0) and LA(v, depth(v)). In the former case, the answer is always the root of the tree and in the latter case, the answer is the node v itself.

Jump Pointer Algorithm

The jump pointer algorithm is a simple algorithms that pre-processes a tree in O(n log n) time and answers level ancestor queries in O(log n) time. The jump pointer algorithm associates up to log n pointers to each vertex of the tree. These pointers are called jump pointers because they jump up the tree towards the root of the tree. For a given node v of a tree, the algorithm stores an array of length l jumpers where l=$\lfloor$log₂(depth(v))$\rfloor$. The i^th element of this array points to the 2ⁱth ancestor of v. Using such data structure helps us jump half way up the tree from any given node. When the algorithm is asked to process a query, we repeatedly jump up the tree using these pointers. Observe that the number of jumps will be at most log n and therefore queries can be answered in log n time.