Lowest common ancestor with Range Minimum Query

Lowest common ancestor with Range Minimum Query

We already have discussed least common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find Least common ancestor of two given nodes.  This is post will concentrate on finding Lowest common ancestor with Range Minimum Query. LCA of (u,v) is the node which is furthest from root and u and v are descendent of it. For example, LCA of (5,9) is 2.

LCA using RMQ

In earlier solutions, we were scanning tree each time a query if fired to find LCA of two nodes which has complexity of O(n). If this query if fired frequently, this operation may become bottleneck. One way to avoid processing all nodes when LCA is asked, is to preprocess tree and store that information in such a way that LCA can be found instantly, say in O(1).

This pattern is very similar to Range Query Minimum algorithm. Can we reduce lowest common ancestor problem to range query minimum problem?

Reduction of LCA to RMQ

Let’s revise what is RMQ : Given array A of length n.  RMQA(i,j) – returns the index of the smallest element in the subarray A[i..j].  Suppose an algorithm has:  Preprocessing time –  Query time –  Notation for the overall complexity of an algorithm: <f(n), g(n) >.

Let’s find LCA of two nodes 5 and 8 manually in above graph. We notice that LCA(u,v) is shallowest common node (in terms of distance from root) which is visited when u and v are visited using depth first search of tree.  Important thing to note is that we are interested in shallowest, which is minimum depth, node between u and v. Sounds like RMQ?

Implementation wise, tree is traversed as Euler tour. At most there can be 2n-1 nodes in Euler tour of tree, store this tour in an array of  2n-1. Then we require depth of each node while doing Euler tour, so we store this information in another arrays of size 2n-1. Any depth would do as far as consistency is maintained, but we will store depth when node was visited first.

1. Euler Tour [1,..,2n-1] – The nodes visited in an Euler tour of T. Euler[i] is the label of the ith node visited in the tour. 
2. Depth[1,..2n-1] – The level of the nodes tour. Level[i] is the level of node Euler[i]. (level is defined to be the distance from the root).
3. FirstVisited[1,..n] – FirstVisited[i] will hold value when node is first visited.

For example of this computation

lowest common ancestor using range minimum query example

To compute LCA(u,v):  All nodes in the Euler tour between the first visits to u and v are E[FV[u],..,FV[v]] (assume FV[u] < FV[v]). 

The shallowest node in this sub-tour is at index RMQ D(FV[u],FV[v]), since D[i] stores the depth of node at E[i]. 

RMQ will return index of shallowest node between u and v, thus output node will be E[RMQ D(FV[u],FV[v])] as LCA(u,v)

lca using rmq example

lowest common ancestor using range minimum query implementation

Beauty of this algorithm to find lca using rmq is that it can be used to find LCA of any tree not just only binary tree or BST. Complexity of algorithm to find lowest common ancestor using range minimum query is <O(n), O(1)> with additional space complexity of O(n).

Please share if there is something wrong or missing, we would love to hear from you. If you are interest in contributing to algorithms and me,please refer to publisher page.