Sunday, 24 August 2014

Lowest Common Ancestor

#include<stdio.h>

struct Node
{
    int data;
    Node *left;
    Node *right;
};
int LCA ( Node* head,int n1,int n2 )
{
    if ( head==NULL )
    {
        return 0;
    }
    if ( head->data<n1 && head->data <n2 )
    {
        return LCA ( head->right, n1, n2 ) ;
    }
    if ( head->data>n1 && head->data >n2 )

    {
        return  LCA ( head->left, n1, n2 ) ;
    }
    return head->data;

}
struct Node* newNode ( int data )
{
    struct Node* node = new  Node ;
    node->data  = data;
    node->left  = node->right = NULL;
    return ( node );
}

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;

    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    n1 = 14, n2 = 8;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2,LCA ( root, n1, n2 ) );

    n1 = 10, n2 = 22;
 
    printf ( "LCA of %d and %d is %d \n", n1, n2, LCA ( root, n1, n2 ) );

    getchar();
    return 0;
}


No comments:

Post a Comment