C++ Program to Find the Lowest Common Ancestor of a 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 :

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
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.

Note: Join free Sanfoundry classes at Telegram or Youtube
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<conio.h>
  5. #include <stdio.h>
  6. #include<iostream>
  7. using namespace std;
  8. struct node
  9. {
  10.     int data;
  11.     struct node *left, *right;
  12. };
  13. /*
  14.  * class declaration
  15.  */
  16. class BST
  17. {
  18. public:
  19.     struct node *lca(struct node *root, int node_1, int node_2)
  20.     {
  21.         if (root != NULL)
  22.         {
  23.             if (root->data > node_1 && root->data > node_2)
  24.             {
  25.                 return lca(root->left, node_1, node_2);
  26.             }
  27.             if (root->data < node_1 && root->data < node_2)
  28.             {
  29.                 return lca(root->right, node_1, node_2);
  30.             }
  31.             return root;
  32.         }
  33.     }
  34.     struct node *newNode(int data)
  35.     {
  36.         struct node *p = NULL;
  37.         p = new node;
  38.         p->data = data;
  39.         p->left = p->right = NULL;
  40.         return(p);
  41.     }
  42. };
  43. int main()
  44. {
  45.     BST b1;
  46.     struct node *root = b1.newNode(20);
  47.     root->left = b1.newNode(8);
  48.     root->right = b1.newNode(22);
  49.     root->left->left = b1.newNode(4);
  50.     root->left->right = b1.newNode(12);
  51.     root->left->right->left = b1.newNode(10);
  52.     root->left->right->right = b1.newNode(14);
  53.     /* Sample tree
  54.      *        20
  55.      *      /    \
  56.      *     8     22
  57.      *    /  \
  58.      *   4   12
  59.      *      /  \
  60.      *     10  14
  61.      */
  62.     int node_1 = 10, node_2 = 14;
  63.     struct node *t = b1.lca(root, node_1, node_2);
  64.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  65.     node_1 = 14, node_2 = 8;
  66.     t = b1.lca(root, node_1, node_2);
  67.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  68.     node_1 = 10, node_2 = 22;
  69.     t = b1.lca(root, node_1, node_2);
  70.     printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);
  71.     getch();
  72. }
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. So as a result we recursively call the function by passing parameters as root->left, node_1 and node_2 now.
4. 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.