#### Tree

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;
}```