Lowest common ancestor in binary tree

Lowest common ancestor 

Given a binary tree, find lowest common ancestor of two given nodes. For example, in given binary tree, lowest common ancestor of node 9  and node 5 will be 2.
lowest common ancestor
We do not have luxury of BST property here, think of something else here.
What is the condition for a node to be Lowest common ancestor (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 ancestors but they are not lowest. How can we find where paths are diverging?

Algorithm to find least common ancestor in binary tree

1. Find any one given node in binary 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 second node resides on other side of parent, then parent is LCA.
4. If it does not, continue to check parent of parent, till we reach root.
5. If we don't find any such node while moving up, LCA is the node which is found in step 1.

Lowest common ancestor : 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

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.

Node *lowestCommonAncestor(Node *node, int val1, int val2){
        if(!node)
                return NULL;
        if(node->value == val1 || node->value == val2)
                return node ;
 
        Node *l = lowestCommonAncestor(node->left, val1, val2);
        Node *r = lowestCommonAncestor(node->right, val1, val2);

       /*if we have found one node on right side of node 
         and other on left side
        then the given node is LCA */
        if(l && r)
                return node;

        /* if we have found one node on the left side,
         we don't look below that node, and we return 
         to parent node to look for right sub tree for 
         the other node */
        if(l)
            return l;

        /* if we have found one node on the right side, 
         we don't look below that node, and we return 
         to parent node to check if other node was found 
         in the left tree then return LCA */
        if(r)
            return r;
}

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).

Please share if there is something missing or wrong. If you are interested in contributing to website, please contact us.