# 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 :

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

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.