Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
1
This again is a famous interview question asked in the past by Microsoft / Google and other such places. We assume a basic knowledge of binary tree. In a quick recap a binary tree is a linked data structure in which each node has two children nodes, a left and a right child. The tree starts at a root node. The special property which makes it a binary search tree is, that every left child is less than its parent and right child is greater than the parent node.
The best way to illustrate this problem is to use a diagram. In the following tree
BSTCommonAncestor.jpg 36.35K
80 downloadsThe nearest common ancestor node of say 19 and 23 is 21. The problem asks for writing a general mechanism to do that.
How would you think of approaching this problem? Will the common tree traversal recursive approach would be of any use?
http://forum.codecal...arch-trees.html
Also if basic BST implementation is needed, it is available
http://forum.codecal...comparison.html
http://forum.codecal...ementation.html
One intuitive approach that comes to mind is, traverse (starting from root node) through the tree for each of the two elements while storing each ancestor node in a separate array. Once you are done with both, you have two arrays each containing intermediate nodes used to reach the end node. We can iterate through both arrays while comparing each element. The node where ancestors no longer remain common should be the answer.
Let me explain by example. First we search for 19 and the resultant path is 14, 21, 17, 20 and finally 19 itself. Then looking for 23 yields 14, 21, 25 and finally 23. Comparing both the arrays, we find that the last common element for both paths is 21. Hence it is the answer. This would work and is a correct solution.
But it has a few disadvantages.
1. We had to traverse for each of the two elements twice. Searching for each element takes log n in a BST, so it takes 2 * log n running time.
2. We need arrays to store ancestor list or path to each node. This would require some memory that can be significant as the since of tree grows. Again if tree has n nodes we would need two arrays each of size log n.
There exists a better solution. What can that be? Well BST’s have a special property. Each node’s left child is smaller than the nodes value itself and right child is greater. How can that be of any use?
At least we know that the nearest common ancestor’s value would be in between the value of both nodes i.e. it will be greater than that of node which occurs as a left child and smaller than the one which is right child (21 is greater than 19 and less than 23 and this will always be true because of the BST property.
Looking at the above earlier solution, we might be able to notice an important point. Until the node which is the nearest common ancestor, either both nodes are greater OR smaller than the current ancestor on the way. The point where they differ will be the solution we are looking for:
Code follows:
#include<iostream>
using namespace std;
struct tnode
{
int data;
tnode *left;
tnode *right;
};
// Finds the nearest common ancestor node, and return pointer to that node
tnode * nearest_common_ancestor(tnode *root, int val1, int val2)
{
tnode *temp = root;
while(temp != NULL)
{
// Move to right subtree if both values are greater than current node's value
if(temp->data < val1 && temp->data < val2)
temp = temp->right;
// Move to the left subtree if both values are less than current
else if(temp->data > val1 && temp->data > val2)
temp = temp->left;
// we have found the common ancestor
else
break;
}
return temp;
}
Since we at max go up to one of the two nodes, and since the complexity of searching an element in a BST is log n. Hence complexity of this algorithm is also O (log n). It requires only a single iteration / look up and does not need any additional memory as used in the solution initially suggested.
Back to top
