Showing posts with label lowest common ancestor in tree. Show all posts
Showing posts with label lowest common ancestor in tree. Show all posts

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;
}

Contributors

Translate