#### 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 == 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; }