C++ Programming Code Examples

C++ > Computer Graphics Code Examples

Program to Find Lowest Common Ancestor in a Binary Search Tree



Program to Find Lowest Common Ancestor in a Binary Search Tree

This C++ program, using recursion, displays the lowest common ancestor in a BST. A lowest common ancestor is one in which the lowest common parent node of both the argument nodes is found.

    #include<conio.h>

    #include <stdio.h>

    #include<iostream>

    using namespace std;

    struct node

    {

        int data;

        struct node* left, *right;

    }*p = NULL;

    struct node *lca(struct node* root, int n1, int n2)

    {

        if (root == NULL)

    	return NULL;

        if (root->data > n1 && root->data > n2)

            return lca(root->left, n1, n2);

        if (root->data < n1 && root->data < n2)

            return lca(root->right, n1, n2);

        return root;

    } 

    struct node* newNode(int data)

    {

        p = new node;

        p->data = data;

        p->left = p->right = NULL;

        return(p);

    }

    int main()

    {

        struct node *root = newNode(20);

        root->left = newNode(8);

        root->right = newNode(22);

        root->left->left = newNode(4);

        root->left->right = newNode(12);

        root->left->right->left = newNode(10);

        root->left->right->right = newNode(14);

        int n1 = 10, n2 = 14;

        struct node *t = lca(root, n1, n2);

        printf("LCA of %d and %d is %d \n", n1, n2, t->data);

        n1 = 14, n2 = 8;

        t = lca(root, n1, n2);

        printf("LCA of %d and %d is %d \n", n1, n2, t->data);

        n1 = 10, n2 = 22;

        t = lca(root, n1, n2);

        printf("LCA of %d and %d is %d \n", n1, n2, t->data);

        getch();

    }