#include<iostream>
using namespace std;
struct node
{
int data;
struct node* left;
struct node* right;
struct node* next;
};
struct node* createnode(int x)
{
struct node* new_node=new struct node;
new_node->data=x;
new_node->left=NULL;
new_node->right=NULL;
new_node->next=NULL;
return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
if(root)
{
if(root==n1)
{
return 1;
}
else if(root==n2)
{
return 1;
}
else
{
return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
}
}
else
{
return 0;
}
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
if(root)
{
int lf = help_anc(root->left,n1,n2);
int rf = help_anc(root->right,n1,n2);
if(lf==1 && rf==1)
{
return root;
}
else
{
node* lca = Ancestor(root->left,n1,n2);
if(lca!=NULL)
{
return lca;
}
lca = Ancestor(root->right,n1,n2);
return lca;
}
}
else
{
return NULL;
}
}
int main()
{
struct node* root=createnode(1);
root->left=createnode(2);
root->right=createnode(3);
root->left->right=createnode(4);
root->left->left=createnode(5);
root->right->right=createnode(6);
root->right->left=createnode(7);
root->right->right->left=createnode(8);
//root->right->right->left->left=createnode(10);
root->right->right->right=createnode(10);
struct node* n1 = root->right->right->right;
struct node* n2 = root->left->left;
struct node* lca=Ancestor(root,n1,n2);
if(lca)
{
cout<<lca->data<<endl;
}
}
Output:
1
A blog on programming and software design interview problems and solutions. Also there are some application development related stuff.
Pages
Thursday, November 15, 2012
Finding the Lowest Common Ancestor of two given nodes in a Binary Tree
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment