#include
typedef struct node
{
int value;
struct node *right;
struct node *left;
}mynode;
mynode *root;
mynode *add_node(int value);
void levelOrderTraversal(mynode *root);
mynode *closestAncestor(mynode* root, mynode* p, mynode* q);
int main(int argc, char* argv[])
{
mynode *node_pointers[7], *temp;
root = NULL;
// Create the BST.
// Store the node pointers to use later...
node_pointers[0] = add_node(5);
node_pointers[1] = add_node(1);
node_pointers[2] = add_node(-20);
node_pointers[3] = add_node(100);
node_pointers[4] = add_node(23);
node_pointers[5] = add_node(67);
node_pointers[6] = add_node(13);
printf("\n\n\nLEVEL ORDER TRAVERSAL\n\n");
levelOrderTraversal(root);
// Calculate the closest ancestors of a few nodes..
temp = closestAncestor(root, node_pointers[5], node_pointers[6]);
printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
node_pointers[5]->value,
node_pointers[6]->value,
temp->value);
temp = closestAncestor(root, node_pointers[2], node_pointers[6]);
printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
node_pointers[2]->value,
node_pointers[6]->value,
temp->value);
temp = closestAncestor(root, node_pointers[4], node_pointers[5]);
printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
node_pointers[4]->value,
node_pointers[5]->value,
temp->value);
temp = closestAncestor(root, node_pointers[1], node_pointers[3]);
printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
node_pointers[1]->value,
node_pointers[3]->value,
temp->value);
temp = closestAncestor(root, node_pointers[2], node_pointers[6]);
printf("\n\nClosest ancestor of [%d] and [%d] is [%d]\n\n",
node_pointers[2]->value,
node_pointers[6]->value,
temp->value);
}
// Function to add a new node to the tree..
mynode *add_node(int value)
{
mynode *prev, *cur, *temp;
temp = (mynode *) malloc(sizeof(mynode));
temp->value = value;
temp->right = NULL;
temp->left = NULL;
if(root==NULL)
{
printf("\nCreating the root..\n");
root = temp;
return;
}
prev=NULL;
cur=root;
while(cur!=NULL)
{
prev=cur;
cur=(valuevalue)?cur->left:cur->right;
}
if(value < prev->value)
prev->left=temp;
else
prev->right=temp;
return(temp);
}
// Level order traversal..
void levelOrderTraversal(mynode *root)
{
mynode *queue[100] = {(mynode *)0};
int size = 0;
int queue_pointer = 0;
while(root)
{
printf("[%d] ", root->value);
if(root->left)
{
queue[size++] = root->left;
}
if(root->right)
{
queue[size++] = root->right;
}
root = queue[queue_pointer++];
}
}
// Function to find the closest ancestor...
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
Here is the tree for you to visualize...
5 (node=0)
1 (node=1) 100 (node=3)
-20 (node=2) 23 (node=4)
13 (node=5) 67 (node=6)
Here is the output...
LEVEL ORDER TRAVERSAL
[5] [1] [100] [-20] [23] [13] [67]
Closest ancestor of [67] and [13] is [23]
Closest ancestor of [-20] and [13] is [5]
Closest ancestor of [23] and [67] is [100]
Closest ancestor of [1] and [100] is [5]
Closest ancestor of [-20] and [13] is [5]
**
