Thursday, October 25, 2012

Program to find Lowest Common Ancestor of two nodes

To find a Lowest or Least Common Ancestor of binary tree we need to pass three arguments .Those are root node of binary tree and the node details to find common ancestor (here node data's are used) . The following code recursively searches for the nodes that we need to find. When it finds the node it returns the node. If both the left and right side of the node returns the node this is it(the node is called as common ancestor) .Else the process will continue until it finds the common ancestor.

For an Example 
In the following tree
                 10
               /      \
             5         12
           /   \
         3      8
                /
               7

for nodes 7 and 3 LCA(Lowest Common Ancestor) is 5.

Code (Written in C):
struct node* lowestCommonAncestor(struct node* node, int n1,int n2)
{
if(node==NULL)
return NULL;

if(node->data==n1 || node->data ==n2)
return node;
else
{
struct node* left,right;
left=lowestCommonAncestor(node->left,n1,n2);
right=lowestCommonAncestor(node->right,n1,n2);

if(left&&right)
return node;
else
return left==NULL?right:left;
}
}