Q:

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

mahmoud2506
Save to bookmark
|
2022-04-30
|
  229 
0

Lowest Common Ancestor in a BST

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
C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

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

Example with explanation:

    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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | tree
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given a string that contains ternary expressions. ... >>
<< Given a Binary Tree, Print the corner nodes at eac...