Lowest Common Ancestor in a Binary Search Tree
#include <stdio.h>
#include <stdlib.h>
struct btnode
{
int value;
struct btnode *l;
struct btnode *r;
}*root = NULL, *temp = NULL, *t2, *t1;
void create()
{
int data;
printf("Enter data of node to be inserted : ");
scanf("%d", &data);
temp = (struct btnode *)malloc(1*sizeof(struct btnode));
temp->value = data;
temp->l = temp->r = NULL;
}
void search(struct btnode *t)
{
if ((temp->value > t->value) && (t->r != NULL))
search(t->r);
else if ((temp->value > t->value) && (t->r == NULL))
t->r = temp;
else if ((temp->value < t->value) && (t->l != NULL))
search(t->l);
else if ((temp->value < t->value) && (t->l == NULL))
t->l = temp;
}
void insert()
{
create();
if (root == NULL)
root = temp;
else
search(root);
}
void inorder(struct btnode *t)
{
if (root == NULL)
{
printf("No elements in a tree to display");
return;
}
if (t->l != NULL)
inorder(t->l);
printf("%d -> ", t->value);
if (t->r != NULL)
inorder(t->r);
}
int size(struct btnode* root)
{
if(root->l==NULL&& root->r==NULL)
return 1;
if(root->l!=NULL && root->r==NULL)
return 1+size(root->l);
if(root->r!=NULL && root->l==NULL)
return 1+size(root->r);
return (size(root->l)+size(root->r))+1;
}
void lowest_common_ancestor(struct btnode* root,int n1,int n2)
{
if(root->value>n1 && root->value>n2)
{
lowest_common_ancestor(root->l,n1,n2);
}
if(root->value<n1 && root->value<n2)
{
lowest_common_ancestor(root->r,n1,n2);
}
if((root->value)<n2 && (root->value)>n1)
{
printf("Lowest Common ancestor is %d",root->value);
}
}
int main()
{
int ch;
int a1,a2,num;
while(1)
{
printf("\n");
printf("OPERATIONS ---\n");
printf("1.Insert an element into tree\n");
printf("2.Inorder Traversal\n");
printf("3.Lowest common Ancestor \n");
printf("4 Exit\n");
printf("Enter your choice : ");
scanf("%d", &ch);
switch (ch)
{
case 1:
insert();
break;
case 2:
inorder(root);
break;
case 3:
printf("Enter the 2 nodes who's lowest ancestor has to found\n");
scanf("%d",&a1);
scanf("%d",&a2);
lowest_common_ancestor(root,a1,a2);
break;
case 4:
exit(0);
default :
printf("Wrong choice, Please enter correct choice ");
break;
}
}
return 0;
}

No comments:
Post a Comment