Lowest Common Ancestor - RahulKushwaha/Algorithms GitHub Wiki

Definition:

Given a tree and two vertices, x and y, Lowest Common Ancestor refers to the closest vertex to the root on the simple path from x to y.

Euler Tour

Euler Tour of a tree is a type of Depth First Traversal starting from the root in which each edge is visited once(going down and going up the edge is considered one visit). Vertices with more children will be traversed multiples times(depending on the number of children).

Euler Tour: 1 2 4 2 5 2 1 3 6 3 7 8 7 3 1

Reduction

LCA problem can be reduced to RMQ problem. We can observe that LCA of two nodes, x and y, is actually equal to the node which is closest to the root on the Euler Tour from x to y. And by closest to root we say minimum height. Therefore LCA(x, y) = E[RMQ(Height of all the nodes on the Euler Tour from x to y)], here RMQ returns the index not the height itself.

Let us see all this with help of example:

Euler Tour
E = [1 2 4 2 5 2 1 3 6 3 7 8 7 3 1]

Heights
H = [0 1 2 1 2 1 0 1 2 1 2 3 2 1 0]

First occurrence in the Euler Tour for all vertices
F = [0 1 7 3 4 8 10 11]

x = 5, y = 8

LCA(5, 8) = E[RMQ(4, 11)]
		  = E[0] = 1

Here we are storing the indices of the Euler Tour Array when a particular vertex was first encountered. Each index, i, of the F array refers to i + 1 vertex in the tree. As we have only elements hence the size of F array.