**How to verify whether a binary tree is a binary search tree?**

__Question:__
For example, the tree in Figure 1 is a binary search tree.

Figure 1: A binary search tree |

A node in binary tree is defined as:

struct
BinaryTreeNode

{

int nValue;

BinaryTreeNode* pLeft;

BinaryTreeNode* pRight;

};

**Binary search tree is an important data structure. It has a specific character: Each node is greater than or equal to nodes in its left sub-tree, and less than or equal to nodes in its right sub-tree.**

__Analysis:__

*Solution 1: Verify value range of each node*
If a binary search tree is scanned with pre-order traversal
algorithm, the value in a root node is accessed to at first. After the root
node is visited, it begins to scan nodes in the left sub-tree. The value of
left sub-tree nodes should be less than or equal to the value of the root node.
If value of a left sub-tree node is greater than the value of the root node, it
violates the definition of binary search tree. It is similar for the right
sub-tree.

Therefore, when it visits a node in binary search tree, it
narrows the value range of left sub-tree and right sub-tree under the current
visited node. All nodes are visited with the pre-order traversal algorithm, and
their value is verified. If value in any node violates its corresponding range,
it is not a binary search tree.

The following sample code is implemented based on this pre-order
traversal solution:

bool
isBST_Solution1(BinaryTreeNode* pRoot)

{

int min =
numeric_limits<int>::min();

int max =
numeric_limits<int>::max();

return
isBSTCore_Solution1(pRoot, min, max);

}

bool
isBSTCore_Solution1(BinaryTreeNode* pRoot, int
min, int max)

{

if(pRoot ==
NULL)

return true;

if(pRoot->nValue
< min || pRoot->nValue > max)

return false;

return
isBSTCore_Solution1(pRoot->pLeft, min, pRoot->nValue)

&& isBSTCore_Solution1(pRoot->pRight, pRoot->nValue,
max);

}

In the code above, value of each node should be in the range
between min and max. The value of the
current visited node is the maximal value of its left sub-tree, and the minimal
value of its right sub-tree, so it updates the min and max arguments and verifies sub-trees recursively.

*Solution 2: Increasing in-order traversal sequence*
The first solution is based on pre-order traversal
algorithm. Let us have another try on in-order traversal. The in-order
traversal sequence of the binary search tree in Figure 1 is: 4, 6, 8, 10, 12,
14 and 16. It is noticeable that the sequence is increasingly sorted.

Therefore, a new solution is available: Nodes in a binary
tree is scanned with in-order traversal, and compare value of each node
against the value of the previously visited node. If the value of the previously
visited node is greater than the value of current node, it breaks the
definition of binary tree.

This solution might be implemented in C++ as the following
code:

bool isBST_Solution2(BinaryTreeNode*
pRoot)

{

int prev =
numeric_limits<int>::min();

return
isBSTCore_Solution2(pRoot, prev);

}

bool
isBSTCore_Solution2(BinaryTreeNode* pRoot, int&
prev)

{

if(pRoot ==
NULL)

return true;

return
isBSTCore_Solution2(pRoot->pLeft, prev) //
previous node

&& (pRoot->nValue >=
prev) // current node

&&
isBSTCore_Solution2(pRoot->pRight, prev = pRoot->nValue); // next node

}

The argument prev of the function isBSTCore_Solution2 above is the value of the previously visited
node in pre_order traversal.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going
to use part of or the whole of this ariticle in your blog
or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

According to me Second Soln doesnt work.

ReplyDeleteTestcase:

-----100

--50

----150

(100->left=50; 50->right=150)

It should be like some thing like this:

bool isBST(Node* root,int &prev) // prev=INT_MIN

{

if(!pNode)

return true;

return isBSTCore_Solution2(pRoot->m_pLeft,prev) && (pRoot->m_nValue >= prev)

&& (prev=pRoot->mValue || true) // Update prev

&& isBSTCore_Solution2(pRoot->m_pRight,prev);

}

Thanks for devendraiit's comments. It is correct that the argument for prev should be passed by reference. I have modified my code in the post.

DeleteBest way to find that IsBST()

Delete1. Travel in-order and store the elements in an array.

2. if the array is sorted then its a BST otherwise not.

Nishikant Sahu

But order of n space complexity:(

DeleteWhy can't you just preorder walk the tree and confirm at each step that the left node (if it exists) is less than the parent, and the right node (if it exists) is greater than the parent?

ReplyDeletewhat about ancestors..?u can't keep track of them with your current proposed method.

DeleteWhy do ancestors matter? In a BST, every node meets the requirement that child->left < node > child->right. So if you recursively verify this condition you have verified that the tree is a BST.

DeleteThis is the same solution as walking the tree in-order and dumping it to an array and then verifying the array is in sorted order, just without the array step.

I'm honestly asking what you might see wrong with this approach, as it worked on all the test cases I gave it.

Well heck, I googled it and yeah looks like you're right, my method will pass incorrect trees.

DeleteHowever there is a much easier fix: simply retain a min/max value and pass that down the tree as you verify.

I maintain that the solution devised above is inefficient.

@Unknown guy:

DeleteThe first solution is doing exactly what you are suggesting. When you traverse pre-order, you are updating the new min/max value(s) as you go down the tree.

I was asked the question and I had a slightly different solution as the first solution above, which was as follows:

ReplyDeletebool validate(TreeNode* root, int min, int max) {

if (!root || (!root->right && !root->left) ) {

return true;

}

if (root->left && (root->left->value > root->value || (root->left->value > max || root->left->value < min))) {

return false;

}

if (root->right && (root->right->value < root->value || (root->right->value > max || root->right->value < min))) {

return false;

}

return validate(root->left, min, root->value) && validate(root->right, root->value, max);

}

I think this recurses less number of times. However, I had forgotten to check whether left node's value is less than min, or right node's value is more than max. So, I was rejected for that.

I think another approach will be compare each node with it parent node. left node <= parent node <= right node.

ReplyDeleteHere is recursive call:

private int isBST(Node node) {

if (node == null) {

return 0;

}

int cmp = node.left == null ? 0 : node.left.key.compareTo(node.key);

int cmp1 = node.right == null ? 0 : node.right.key.compareTo(node.key);

if (cmp <= 0 && cmp1 >= 0) {

int n1 = isBST(node.left);

int n2 = isBST(node.right);

if (n1 != 0 || n2 != 0) {

return -1;

} else {

return 0;

}

} else {

return -1;

}

}

This comment has been removed by the author.

DeleteTushar Goyal, your approach will return TRUE for certain binary tress that are not BST.

DeleteTest Example:

-------------------10

-------------------/--\

------------------/----\

----------------5-----20

---------------/--\

--------------/----\

-------------2----50

Clearly, 5<10<20 and 2<5<50, so your suggested algorithm will pass the tests even when this is not a BST

in the function(isBSTcore_solution1) of the in_order traverse the min value can be equal to the proot->nvalue and greater or less than proot->nvalue .but you checked only the greater than or less than condition.

ReplyDelete