Friday, November 18, 2016

Lowest common Ancestor in tree

#include <iostream>
using namespace std;

struct node
{
int data;
node *left;
node *right;
};

void printTree(node *t){
if(t){
cout<<t->data<<" ";
printTree(t->left);
printTree(t->right);
}
}
node *getNode(int d){

node *temp = new node;
temp->data = d;
temp->left=temp->right = NULL;
return temp;
}
bool isPresent(node *t,int a)
{
if(t!=NULL){
if(t->data==a||isPresent(t->left,a)||isPresent(t->right,a))
return true;
}
return false;
}
node *commonAncestor(node *t,int a,int b)
{
static int count =0;
if(t!=NULL)
{
if((isPresent(t->left,a)&&isPresent(t->right,b))||(isPresent(t->right,a)&&isPresent(t->left,b)))
return t;
node *p= commonAncestor(t->left,a,b);

if(p)
return p;
else
return commonAncestor(t->right,a,b);
}
return NULL;
}
int main (){

node *t = getNode(5);
t->left= getNode(2);
t->right= getNode(7);
t->left->left= getNode(12);
t->right->right= getNode(17);
t->left->right= getNode(21);
t->right->left= getNode(71);
printTree(t);
node *p = commonAncestor(t,71,17);
if(p==NULL)
cout<<"NO common Ancestor";
else
cout<<"common ancestor is "<<p->data;
}

No comments:

Post a Comment

Contributors

Translate