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

Are you looking to learn the topic of “C++ Program to Find Lowest Common Ancestor in a Binary Search Tree”? If yes then you are in the perfect tutorial. Let’s move on to this tutorial directly.

Program Code

/*
* 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();
}

Final Thoughts 