**Problem :- **

Find the Least Common Ancestor (** LCA **) of two nodes in a **Binary Search Tree**.

**LCA** of two nodes **x** and **y**
in a **BST** is the lowest node in the tree which contain both **x** and **y** as descendants.

For the Binary Search Tree shown below, **LCA** of nodes **2** and **20** is **15** .

Similarly, **LCA** of nodes **5** and **30** is **25** .

**Solution :- **

Suppose we want to find the **LCA** of two nodes **x** and **y**.

We will recursively traverse the **BST** and try to find the first node **P** whose value lies between **x** and **y**
i.e ** ( x->data < P->data < y->data )** or **( y->data < P->data < x->data )**.
**P** is the **LCA**.

We start at root node **R**. **R** is the **LCA** if any of the following conditions are satisfied :

If **R -> left == x or R -> left == y**

If **R -> right == x or R -> right == y** .

If **x < R < y or y < R < x**

If value of **R** is greater than value of both the nodes, then the **LCA** lies in left subtree of **R** and if **R**'s value is
less than value of both the nodes, the the **LCA** lies in right subtree of **R** .

See the implementation below.

**#include<iostream>**
**using namespace** std;
*// node structure*
**typedef struct** tree_node
{
**int** value;
**struct** tree_node *left, *right;
}node;
*// create a new node*
node *getNewNode(**int** value) {
node *new_node = **new** node;
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
**return** new_node;
}
*// create the tree*
node *createTree() {
node *root = getNewNode(25);
root->left = getNewNode(15);
root->right = getNewNode(30);
root->left->left = getNewNode(5);
root->left->right = getNewNode(20);
root->left->left->left = getNewNode(2);
root->right->right = getNewNode(40);
**return** root;
}
*//computes the LCA
//assumes both the values are present in the tree*
**int** findLCA(node *root, **int** n1, **int** n2) {
**if** (root == NULL || root->value == n1 || root->value == n2)
**return** -1; *//no LCA*
**if** (root->left != NULL && root->left->value == n1 || root->left->value == n2)
**return** root->value; *// current root is the LCA*
**if** (root->right != NULL && root->right->value == n1 || root->right->value == n2)
**return** root->value; *// current root is the LCA*
**if** ((root->value > n1 && root->value < n2) ||
(root->value > n2 && root->value < n1))
**return** root->value; *// current root is the LCA*
**if** (root->value > n1 && root->value > n2)
**return** findLCA(root->left,n1,n2); *// LCA is present in left subtree*
**else
return** findLCA(root->right,n1,n2); *// LCA is present in right subtree *
}
*//main*
**int** main() {
node *root = createTree();
**int** n1 = 5, n2 = 30;
**int** lca = findLCA(root,n1,n2);
cout<<"\nLCA of "<<n1<<" & "<<n2<<" is "<<lca;
cout<<endl;
**return** 0;
}