Lowest common ancestor in binary tree

Lowest common ancestor in binary tree 

Given a binary tree (not a binary search tree, refer Post for that), find the lowest common ancestor of two given nodes.

Don’t want read, watch video here 🙂


Analysis

We do not have luxury of BST property here so we need to think of something else here.
What is the condition for a node to be LCA of two nodes. Condition is that paths for both given nodes should diverge from the candidate node.Till the time we have path common for given nodes, we have common ancestor but they are not lowest. How can we find where paths are diverging? Here is how: 

Algorithm to find least common ancestor in binary tree

  1. Find any one node in the tree.
  2. Once one node is found, move up to parent and check if other resides on the other side of the parent.
  3. If other resides on other side of the parent, then parent is LCA.
  4. If it does not, continue to check parent of parent, till we have reached root.
  5. If we don’t find any such node while moving up, LCA is the node which is found in step 1.

Implementation

For every node in tree, check for if any of the given nodes in left side of the node. As soon as we encounter a node which is equals to one of the nodes given, return that node. After that, check for other node in right sub tree of the parent of returned node. If we find other  node on the right side of the parent node, then parent node is LCA.
If we found a node on left side and do not find other on the right side, then other node is below the returned node from left side, hence that node is LCA. If we don’t find any node in the left tree, then both nodes are on the right side of the node, move to right side of the node. Follow the procedure again.
Let’s take an example to see this algorithm work. we have tree as                     

lowest common ancestor
 Binary Search Tree

Find LCA of 2 and 5.For root 6, we would first move to left side and search for 2 and 5 in sub tree root at 3. Again we would search 2 and 5 in left sub tree in tree rooted at 3. In this step we would look for nodes in left sub tree of tree rooted at 2.

This time we would find 2 which is one of the two nodes. We would return node 2, let’s call it left.

Once we get this node we would look on the right side of sub tree of the tree rooted at 3.

Once again, we would hit one of nodes we are looking for i.e. We would return 5.let’s call it right.

Now at node 3 we have both left and right as non-null, hence 3 is the lowest common ancestor.

Tip: We don’t need to look into the left and right tree of the node which is equal to one of nodes we are searching for, as in any case that would be the LCA if we don’t fins other node in right sub tree of parent . (Think loud!).We only need to look into the right part of the parent of the node, if the other node is on the right side of the parent, then this node cannot be LCA, but the parent is the LCA.

If we don’t find other node once we find one, we assume that the found node is the LCA, as other node can be below that node.

Consider another example, find LCA of 2 and 3.
1. We look on the left sub tree of tree rooted at 6.
2. We go to 3. 3 is the node we are looking for. return from here.
3. Check for the other node in right sub tree of parent node i.e 6.
4.  We would not find any of the nodes 2 or 3 on the right side of 6.
5. Hence we return node 3 as LCA.
So there is a problem here, what if there is only one node present in tree. we would report that node as LCA.

Code

Complexity analysis

We would be scanning all nodes at once for comparison with the given nodes, hence worst complexity of finding lowest common ancestor in binary tree will be O(N).

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