Lowest Common ancestor of a Binary Tree.

In this chapter we shall see how to calculate lowest common ancestor in a binary tree.

Problem Statement:

You are given root node of a tree along with 2 nodes. You need to calculate the lowest common ancestor.

Ancestor is the common node between 2 nodes. Hence you are given 2 nodes, you need to calculate the lowest common ancestor.

For example:

For the node d, e the lowest common ancestor is b.
For the node f, g the lowest common ancestor is c.
For the node h, i the lowest common ancestor is a. Because only the root node is common between those 2 nodes.

Now let’s see how to solve this.

One simple way to achieve this is to list down all the path from root node to the node in question and select the lowest common node between 2 nodes.

It the path for “d” is
a -> b -> d.

The path for “e” is:

a -> b -> e

as you can see that a, b nodes are same for both of the path. We need to select the lowest node i.e “b”.

Another approach is to solve by using recursion without using any extra space.

Below are the steps on how to perform:

We follow bottom up approach to get to solution. The basic idea is that we return current node to it’s patent if we find the node. If we don’t find the node we return NULL.

We do this for both left and right children of the node and finally arrive at the result.

Below is the pseudo code for the same.

node return_lca(node *curr, node a, node b)
{
	if curr == null
		return null

	if curr == A || curr == B
		return curr;

	left = return_lca(curr.get_left(), a, b) 
	right = return_lca(curr.get_right(), a, b) 

	if (left != NULL & right != NULL)
		return curr

	if left == NULL
		return right
	else
		return left;
}

Let’s see with help of an example:

For the image below, we need to find the lowest common ancestor for h and i nodes.

Initially we take the left nodes of “a” we reach node h, as we have found out a node, we return that node to it’s patent node “d” as below:

Now node “d” is not having any right child. Hence, node “d” will return it’s value, to it’s parent node “b” as shown below:

Now node “b” is having right child. We found the “i” value, first we return i to e. Then as e node is not having any left child, we return the node value to it’s parent node “b”.

Now node “b” has both left and right child, hence return the value “b” to it’s parent “a”. For node “a”, the right child will return null because the needed nodes are not present.

Hence the result will be “b”.