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

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.

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.

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

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.

`/*`

`* C++ Program to Find Lowest Common Ancestor in a Binary Search Tree`

`*/`

`#include<conio.h>`

`#include <stdio.h>`

`#include<iostream>`

using namespace std;

`struct node`

`{`

int data;

struct node *left, *right;

};

`/*`

`* class declaration`

`*/`

`class BST`

`{`

public:

struct node *lca(struct node *root, int node_1, int node_2)

`{`

if (root != NULL)

`{`

if (root->data > node_1 && root->data > node_2)

`{`

return lca(root->left, node_1, node_2);

`}`

if (root->data < node_1 && root->data < node_2)

`{`

return lca(root->right, node_1, node_2);

`}`

return root;

`}`

`}`

struct node *newNode(int data)

`{`

struct node *p = NULL;

p = new node;

p->data = data;

p->left = p->right = NULL;

return(p);

`}`

};

int main()

`{`

`BST b1;`

struct node *root = b1.newNode(20);

root->left = b1.newNode(8);

root->right = b1.newNode(22);

root->left->left = b1.newNode(4);

root->left->right = b1.newNode(12);

root->left->right->left = b1.newNode(10);

root->left->right->right = b1.newNode(14);

`/* Sample tree`

`* 20`

`* / \`

`* 8 22`

`* / \`

`* 4 12`

`* / \`

`* 10 14`

`*/`

int node_1 = 10, node_2 = 14;

struct node *t = b1.lca(root, node_1, node_2);

printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);

node_1 = 14, node_2 = 8;

t = b1.lca(root, node_1, node_2);

printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);

node_1 = 10, node_2 = 22;

t = b1.lca(root, node_1, node_2);

printf("LCA of %d and %d is %d \n", node_1, node_2, t->data);

getch();

`}`

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.

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