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