#### Tree

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 && (root->value == n1 || root->value == n2)) return root->value;
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;
}```