C Program to find the Lowest Common Ancestor of a given Binary Search Tree

«
»

This is a C Program to find the Lowest Common Ancestor of a given tree.

Problem Description

We will be given a Binary Tree and we have to write a C program to find out the Lowest Common Ancestor of the two nodes of same tree taken as input from user.
Lowest Common Ancestor: In a given tree, the lowest common ancestor of two nodes node_1 and node_2 will be a node X such that node X will be the lowest node who has node_1 and node_2 as its descendants or children.

Expected Input and Output

Case 1. When both the nodes lie on same side of the root node and at same level:
For example :

advertisement
If the input tree is 
             20
           /    \
          8     22
         /  \
        4   12
           /  \
          10  14
and the nodes are node_1 = 10, node_2 = 14,
then Output will be LCA = 12.

Case 2. When one of the nodes itself is a lowest common ancestor:
For example :

If the input tree is 
             20
           /    \
          8     22
         /  \
        4   12
           /  \
          10  14
and the nodes are node_1 = 14, node_2 = 8,
then Output will be LCA = 8.

Case 3. When the two nodes lie on different sides of root node:
For example :

advertisement
If the input tree is 
             20
           /    \
          8     22
         /  \
        4   12
           /  \
          10  14
and the nodes are node_1 = 10, node_2 = 22,
then Output will be LCA = 20.
Problem Solution

1. First we need to look for node_1 and node_2 in given tree. If they lie on different sides of root node, then the root itself will be the LCA of node_1 and node_2.
2. If root is greater than node_1 and node_2 then their LCA will lie on left subtree.
3. If root is less than node_1 and node_2, their LCA will lie on right subtree.

Program/Source Code

Here is source code of the C Program for finding the lowest common ancestor of of nodes in a given binary search tree. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on windows 10. The program output is also shown below.

  1. /*
  2.  * C Program to Find Lowest Common Ancestor in a Binary Search Tree
  3.  */
  4. #include <stdio.h>
  5. #include<stdlib.h>
  6. struct node
  7. {
  8.     int data;
  9.     struct node *left, *right;
  10. };
  11. /*
  12.  * Function to find the lowest common ancestor
  13.  */
  14. struct node *lca(struct node *root, int node_1, int node_2)
  15. {
  16.     if (root != NULL)
  17.     {
  18.         if (root->data > node_1 && root->data > node_2)
  19.         {
  20.             return lca(root->left, node_1, node_2);
  21.         }
  22.         if (root->data < node_1 && root->data < node_2)
  23.         {
  24.             return lca(root->right, node_1, node_2);
  25.         }
  26.         return root;
  27.     }
  28. }
  29. struct node *newNode(int data)
  30. {
  31.     struct node* p = (struct node*)malloc(sizeof(struct node));
  32.     p->data = data;
  33.     p->left = p->right = NULL;
  34.     return(p); 
  35. }
  36. int main()
  37. {
  38.     struct node *root = newNode(20);
  39.     root->left = newNode(8);
  40.     root->right = newNode(22);
  41.     root->left->left = newNode(4);
  42.     root->left->right = newNode(12);
  43.     root->left->right->left = newNode(10);
  44.     root->left->right->right = newNode(14);
  45.     /* Sample tree
  46.      *        20
  47.      *      /    \
  48.      *     8     22
  49.      *    /  \
  50.      *   4   12
  51.      *      /  \
  52.      *     10  14
  53.      */
  54.     int node_1 = 10, node_2 = 14;
  55.     struct node *t = lca(root, node_1, node_2);
  56.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  57.     node_1 = 14, node_2 = 8;
  58.     t = lca(root, node_1, node_2);
  59.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  60.     node_1 = 10, node_2 = 22;
  61.     t = lca(root, node_1, node_2);
  62.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  63.     return 0;
  64. }
Program Explanation

1. Here in this program we have written a function to find out the lowest common ancestor of two nodes in a given tree.
2. Function lca(root,node_1,node_2) takes in three parameters which are root node of the tree, node_1 and node_2 are the two nodes whose LCA is to be determined. Function LCA returns a node therefore it is of (struct node *) type.

advertisement

lca(root, node_1, node_2)
1. This function returns the lowest node who has node_1 and node_2 as its descendants or children.
2. If node_1 and node_2 lie on different sides of root i.e. (node_1 > root->data && node_2 < root->data) or vice versa, then the lca will be the root node itself.
3. In other cases such as when both node_1 and node_2 lie on left subtree i.e. (node_1 < root->data && node_2 < root->data), then the lca also lies on left subtree.
4. So as a result we recursively call the function by passing parameters as root->left, node_1 and node_2 now. By passing root->left as a parameter we go deeper and deeper inside the left subtree and return the smallest node which has both the nodes node_1 and node_2 as it’s children.
5. Similarly we do it for the right subtree by checking just one if condition and passing root->right as a parameter.

Runtime Test Cases
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement

Here’s the list of Best Reference Books in C Programming, Data-Structures and Algorithms

If you wish to look at programming examples on all topics, go to C Programming Examples.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn