Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
1
This is an interesting question often asked in programming interviews. For a quick recap a BST is a binary tree in which every left child (and following sub tree) is less than its parent node, and right child (and following sub tree) is greater than the parent node. Obviously, "less than" was referred based upon the value contained inside each node. We will code up a basic BST along.
The motivation for this one came from a few related posts i.e.
http://forum.codecal...earch-tree.html
http://forum.codecal...arch-trees.html
http://forum.codecal...esantation.html
http://forum.codecal...lk-loading.html
I have written the basic structure and function needed to create and iterate through a BST.
struct tnode
{
int data;
tnode *left;
tnode *right;
};
Each time we create a new node, it needs to be allocated and values be filled
tnode * create_node(int value)
{
tnode *new_node = new tnode;
new_node->data = value;
new_node->left = new_node->right = NULL;
return new_node;
}
A simple recursive function to traverse through the BST in order. In order traversal means going to the left child first, then parent and finally to the right child at each level. This is one of the three common traversal mechanisms for trees. Other two being pre and post order traversal.void traverse(tnode *r)
{
if(r == NULL)
return;
traverse(r->left);
cout << r->data << " ";
traverse(r->right);
}
Then we need a function which would be called repeatedly to search for the proper position to insert a new node. It internally calls create node when it has found the proper insertion place.
bool insertnode(tnode * root, int value)
{
tnode *temp = root;
while(1)
{
if(temp->data == value)
return false;
if(temp->data < value)
{
if(temp->right != NULL)
temp = temp->right;
else
{
temp->right = create_node(value);
break;
}
}
else // (temp->data > value)
{
if(temp->left != NULL)
temp = temp->left;
else
{
temp->left = create_node(value);
break;
}
}
}
return true;
}
To be able to get this into running state the contents of main program
int main()
{
tnode * root;
root = create_node(14);
insertnode(root, 6);
insertnode(root, 4);
insertnode(root, 8);
insertnode(root, 2);
insertnode(root, 5);
insertnode(root, 7);
insertnode(root, 10);
insertnode(root, 21);
insertnode(root, 17);
insertnode(root, 19);
insertnode(root, 20);
insertnode(root, 15);
insertnode(root, 18);
insertnode(root, 25);
insertnode(root, 23);
insertnode(root, 27);
traverse(root);
return 0;
}
And here is the BST created from above calls
ChkIfBST.jpg 28.59K
52 downloadsSo far we have created a BST successfully and did a traversal to print it’s values.
Now we come back to our original problem i.e. given a tree validate if it is a BST or not. The first and obvious solution that comes to mind is to use the same traversal algorithm while checking each node for it’s left child being smaller than the parent and right child being greater. This seems to be easy to code and would pass most of the cases.
However, it is not the correct solution.
It would fail for the following case i.e.
8
4
2 10Since we are only validating each level, our first solution would pass the above which is not a BST because 10 occurs in the left subtree of root 8 which should have been on the right.
So basically we need to find a way to check for the entire sub tree of a node rather than just comparing with the current left and right children. A good way to do that is, to start with a MAX and MIN value and gradually keep on tightening those values as we move deeper into sub trees. This way we keep calculating the upper and lower ranges in reach recursive call.
bool validate_bst(tnode *temp, int min, int max)
{
if(temp == NULL)
return true;
if(temp->data > min && temp->data < max)
{
if( validate_bst(temp->left, min, temp->data) &&
validate_bst(temp->right, temp->data, max) )
return true;
}
return false;
}
In main we add the following code to use this function
if (validate_bst(root, -1, 100) ) // Basically we pass -1 as min and 100 as max in
// this instance
cout << "YES" << endl;
else
cout << "NO" << endl;
It validates the above created BST and successfully and would return false no matter how deep a level deviates from BST property.
There is one more solution to this problem. If you look at the results of traverse call as follows,
ChkBST.jpg 29.67K
70 downloadsYou would notice that entire tree is printed in ascending sorted order. This property will always hold for a BST. So if we do an in order traversal and save the results in an array or find another way to just ensure that all elements are sorted, then this would also verify that it is a BST.
Back to top
