**Problem :- **

Find the Least Common Ancestor (** LCA **) of two nodes in a **Binary Tree** .**LCA** of two nodes **x** and **y**
in a Binary Tree is the lowest node in the tree which contain both **x** and **y** as descendants.
For the Binary Tree shown below, **LCA** of nodes **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 have seen previously how **LCA in Binary Search Tree ( BST )** is computed utilizing the properties of **BST** but a normal
binary tree may not follow those properties. So, the technique is different here.

Since our intent is to find the lowest node which is the ancestor of nodes **x** and **y**, we will starting
searching that node from bottom to up in the tree. For each node starting from the bottom-most level, we will check recursively
if we can find a node **P** suct that **x** lies in left subtree of **P** and **y** lies in right subtree or
**x** in right and **y** in left subtree. 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;
}
*// check if a target node is present in a subtree
// starting at a particular node*
**bool** isNodePresent(node *temp, **int** data) {
**if** (temp == NULL) **return false**;
**if** (temp->value == data) **return true**;
**else
return** isNodePresent(temp->left,data) | isNodePresent(temp->right,data);
}
*//computes the LCA*
**int** findLCA(node *root, **int** n1, **int** n2) {
**static bool** lca_found = **false**;
**static int** lca = -1;
**if** (root == NULL)
**return** -1;
*// start traversing from the leaf nodes towards root*
findLCA(root->left,n1,n2); *//check if lca is in left subtree*
findLCA(root->right,n1,n2); *//check if lca is in right subtree*
**if**(!lca_found && (isNodePresent(root->left,n1) && isNodePresent(root->right,n2))
|| (isNodePresent(root->left,n2) && isNodePresent(root->right,n1))) {
lca_found = **true**;
lca = root->value;
}
**return** lca;
}
*//main*
**int** main() {
node *root = createTree();
**int** n1 = 30, n2 = 20;
**int** lca = findLCA(root,n1,n2);
cout<<"\nLCA of "<<n1<<" & "<<n2<<" is "<<lca;
cout<<endl;
**return** 0;
}