Home » programming » Find lowest common ancestor on a tree

Find lowest common ancestor on a tree

Today, with Karolos we were solving some algorithmic problems. We bumped into the problem of finding the lowest common ancestor of two nodes on a tree. Additionally, there is the constraint of disallowing preprocessing.

If you want to try this problem yourself, you can find it on POJ.

Solution

For both of the nodes that we want to find their common ancestor, we traverse the tree until the root. We put into a vector the ancestors. Now, we have two vectors (one for each of the two initial nodes). If the vectors are of different size, that means that one node is in a higher level that the other one. Therefore, we can safely discard the first elements of the smaller vector, since they are in a lower level and they could not be common ancestors.

We end up with two vectors of the same size. We know that the last elements (at least the last one which is the root) are going to be the same. We only want to find the first (=leftmost) common element in both vectors.

We can employ binary search. We start at the middle of both vectors and compare the values. If they are the same, we go to the left, otherwise, we go to the right. We continue, until we made sure that we have found the first position where both elements are the same.

In code, it is simpler.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: