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