Lowest Common Ancestor in a Binary Search Tree

Lowest Common Ancestor in a Binary Search Tree

Here the lowest common ancestor of 12 and 14 is 13 , lca of 1 and 13 is 10 so on . 

#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

All Repeated Words In Text File And Their Occurrences In Java

Find All Repeated Words In Text File And Their Occurrences In Java Place your file location in the argument of the FileReader. If t...