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;
}
}
1 comment:
Good work buddy
Post a Comment