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
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.
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
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:
Example with explanation:
C++ implementation
Output