Home » Interview coding problems/challenges

Lowest Common Ancestor in a BST

In this article, we are going to see how to find lowest common ancestor in a BST? This is a very common problem that has been featured in interview rounds of Amazon, Microsoft and Synopsis. Submitted by Radib Kar, on February 26, 2019

Problem statement

Given a Binary Search Tree and 2 nodes value n1 and n2, your task is to find the lowest common ancestor of the two nodes. Assume that n1 and n2 both existing node value of the tree.

Example

    Input BST:
      8
     /  \
   4    10
  / \    / \
 3  5  9   11

    n1: 9
    n2: 11

    Output:10

    n1: 4
    n2: 10

    Output:8

Solution

The key idea of the solution is while traversing BST from root to bottom, the first node that is encountered with a value between n1 and n2, i.e., n1<node->data<n2, is the Least Common Ancestor(LCA) of those two nodes having values n1, n2 respectively.

So, traverse the BST using pre-order traversal. If we find a node with value in between n1 and n2, the node is the LCA. If its (the currently processed node) value is greater than both n1 and n2, then the LCA lies in the left subtree of the currently processed node and if its (the currently processed node) value is smaller than both n1 and n2 then the LCA must be on the right subtree of the currently processed node.

Algorithm

FUNCTION LCA(root, n1, n2)
    While (true)
        //if root->data lies between n1 and n2 both
        IF ((root->data>=n1 && root->data<=n2)||(root->data<=n1 && root->data>=n2))
            return root; //LCA found
        IF(n1data) //root->data > both n1 & n2
            root=root->left; //go to left
        Else//root->data < both n1 and n2
            root=root->right; //go to right
    END While
END FUNCTION

Explanation with example

    Input BST:
      8
     /  \
   4    10
  / \    / \
 3  5  9   11

n1: 9
n2: 11
Nodes are represented by their respective values
In main we call LCA (8,9,11)

LCA(8,9,11)
root->data<n1 //8<9 ensures root->data smaller than both n1 & n2
root=root->right


LCA(10,9,11)
root->data>n1&& root->data<n2 //10>9&& 10<11 ensures root->data in between n1 & n2
return root//10

Program terminates..
10 is LCA

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Node{
	public:             
	int data;      //value
	Node *left;    //pointer to left child
	Node *right;   //pointer to right child
};

// creating new node
Node* newnode(int data)  
{ 
	Node* node = (Node*)malloc(sizeof(Node)); 
	node->data = data; 
	node->left = NULL; 
	node->right = NULL; 
	return(node); 
}

Node* LCA(Node *root, int n1, int n2)
{
while(true){
	if((root->data>=n1 && root->data<=n2)||(root->data<=n1 && root->data>=n2))
		return root;
	if(n1<root->data)
		root=root->left;
	else
		root=root->right;
	}
}

int main(){
	cout<<"tree is built as per 1st example\n";
	Node *root=newnode(8); 
	
	root->left= newnode(4); 
	root->right= newnode(10); 
	root->right->right=newnode(11);
	root->right->left=newnode(9);
	root->left->left=newnode(3); 
	root->left->right=newnode(5);

	int n1=9, n2=11;

	cout<<"Lowest common ancestor of "<<n1<<" & "<<n2;
	cout<<" is:"<<LCA(root,n1,n2)->data<<endl;
	
	return 0;
}

Output

tree is built as per 1st example
Lowest common ancestor of 9 & 11 is:10