Lowest Common Ancestor in a Binary Search Tree.

June 23, 2019

Find the Least Common Ancestor (LCA ) of two nodes in a Binary Tree .

Introduction

LCA of two nodes a and b in a Binary Tree is the lowest node in the tree which contain both a and b as descendants. 

Suppose we want to find the LCA of two nodes a and b.

Search the lowest node which is the ancestor of nodes a and b, 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 N such that a lies in left subtree of N a and b lies in right subtree or a in right and b in left subtree. Let us understand this with example.

Example

In the tree given below, LCA of nodes 4 and 25 is 20. Similarly, LCA of nodes 10 and 35 is 30. LCA of node 20 and 4 is 20. 

The diagramaticall structure of tree is:

[code language=”css”]

#include<iostream>
using namespace std;

// structure of Node
typedef struct Treenode
{
int val;
struct Treenode *left, *right;
}Treenode;

// create a new node
Treenode *getNNode(int val)
{
Treenode *n_node = new Treenode;
n_node->val = val;
n_node->left = NULL;
n_node->right = NULL;
return n_node;
}

// construct tree
Treenode *constructTree()
{
Treenode *treenode = getNNode(30);
treenode->left = getNNode(20);
treenode->right = getNNode(35);
treenode->left->left = getNNode(10);
treenode->left->right = getNNode(25);
treenode->left->left->left = getNNode(4);
treenode->right->right = getNNode(45);
return treenode;
}

// check for target Treenode
bool NodePresent(Treenode *temp, int d)
{
if (temp == NULL) return false;
if (temp->val == d) return true;
else
return NodePresent(temp->left,d) | NodePresent(temp->right,d);
}

//computes the Lowest Common Ancestor
int searchLCA(Treenode *treenode, int m1, int m2) {
static bool lca_searched = false;
static int Lowest_Common_Ancestor = -1;
if (treenode == NULL)
return -1;
// start traversing from the leaf nodes towards treenode
searchLCA(treenode->left,m1,m2); //check if Lowest_Common_Ancestor is in left subtree
searchLCA(treenode->right,m1,m2); //check if Lowest_Common_Ancestor is in right subtree
if(!lca_searched && (NodePresent(treenode->left,m1) && NodePresent(treenode->right,m2))
|| (NodePresent(treenode->left,m2) && NodePresent(treenode->right,m1))) {
lca_searched = true;
Lowest_Common_Ancestor = treenode->val;
}
return Lowest_Common_Ancestor;
}

/* Program to test above functions */
int main()
{
Treenode *treenode = constructTree();
int m1 = 10, m2 = 45;
int Lowest_Common_Ancestor = searchLCA(treenode,m1,m2);
cout<<"\nLCA of "<<m1<<" & "<<m2<<" is "<<Lowest_Common_Ancestor;
cout<<endl;
return 0;
}

[/code]