Determine if a Binary Tree is a Binary Search Tree (BST)

September 14, 2010 in binary tree

Write a function isBST(BinaryTree *node) to verify if a given binary tree is a Binary Search Tree (BST) or not.

First, you must understand the difference between Binary Tree and Binary Search Tree (BST). Binary tree is a tree data structure in which each node has at most two child nodes. A binary search tree (BST) is based on binary tree, but with the following additional properties:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

This question is a very good interview question, because it really tests your understanding of the definition of BST. Most people will fall to this first trap, and gives the following algorithm:

Assume that the current node’s value is k. Then for each node, check if the left node’s value is less than k and the right node’s value is greater than k. If all of the nodes satisfy this property, then it is a BST.

It sounds correct and convincing, but look at this counter example below: A sample tree which we name it as binary tree (1).

    10
   /  \
  5   15     -------- binary tree (1)
     /  \
    6    20

It’s obvious that this is not a valid BST, since (6) could never be on the right of (10).

Based on BST’s definition, we can then easily devise a brute-force solution:

Assume that the current node’s value is k. Then for each node, check if all nodes of left subtree contain values that are less than k. Also check if all nodes of right subtree contain values that are greater than k. If all of the nodes satisfy this property, then it must be a BST.

Below is the brute force code (though inefficient, but works):

bool isSubTreeLessThan(BinaryTree *p, int val) {
  if (!p) return true;
  return (p->data < val && 
          isSubTreeLessThan(p->left, val) && 
          isSubTreeLessThan(p->right, val));
}

bool isSubTreeGreaterThan(BinaryTree *p, int val) {
  if (!p) return true;
  return (p->data > val && 
          isSubTreeGreaterThan(p->left, val) && 
          isSubTreeGreaterThan(p->right, val));
}

bool isBSTBruteForce(BinaryTree *p) {
  if (!p) return true;
  return isSubTreeLessThan(p->left, p->data) && 
         isSubTreeGreaterThan(p->right, p->data) && 
         isBSTBruteForce(p->left) && 
         isBSTBruteForce(p->right);
}

bool isSubTreeLessThan(BinaryTree *p, int val) {

if (!p) return true;

return (p->data < val &&

isSubTreeLessThan(p->left, val) &&

isSubTreeLessThan(p->right, val));

}

bool isSubTreeGreaterThan(BinaryTree *p, int val) {

if (!p) return true;

return (p->data > val &&

isSubTreeGreaterThan(p->left, val) &&

isSubTreeGreaterThan(p->right, val));

}

bool isBSTBruteForce(BinaryTree *p) {

if (!p) return true;

return isSubTreeLessThan(p->left, p->data) &&

isSubTreeGreaterThan(p->right, p->data) &&

isBSTBruteForce(p->left) &&

isBSTBruteForce(p->right);

}

Solution:
Here is the much better solution. Instead of examining all nodes of both subtrees in each pass, we only need to examine two nodes in each pass.

Refer back to the binary tree (1) above. As we traverse down the tree from node (10) to right node (15), we know for sure that the right node’s value fall between 10 and +INFINITY. Then, as we traverse further down from node (15) to left node (6), we know for sure that the left node’s value fall between 10 and 15. And since (6) does not satisfy the above requirement, we can quickly determine it is not a valid BST. All we need to do is to pass down the low and high limits from node to node! Once we figure out this algorithm, it is easy to code.

bool isBSTHelper(BinaryTree *p, int low, int high) {
  if (!p) return true;
  if (low < p->data && p->data < high)
    return isBSTHelper(p->left, low, p->data) && 
           isBSTHelper(p->right, p->data, high);
  else
    return false;
}

bool isBST(BinaryTree *root) {
  // INT_MIN and INT_MAX are defined in C++'s <climits> library
  return isBSTHelper(root, INT_MIN, INT_MAX);  
}

bool isBSTHelper(BinaryTree *p, int low, int high) {

if (!p) return true;

if (low < p->data && p->data < high)

return isBSTHelper(p->left, low, p->data) &&

isBSTHelper(p->right, p->data, high);

else

return false;

}

bool isBST(BinaryTree *root) {

// INT_MIN and INT_MAX are defined in C++'s <climits> library

return isBSTHelper(root, INT_MIN, INT_MAX);

}

This algorithm runs in O(N) time, where N is the number of nodes of the binary tree. It also uses O(1) space (neglecting the stack space used by calling function recursively).

Alternative Solution:
Another solution is to do an in-order traversal of the binary tree, and verify that the previous value (can be passed into the recursive function as reference) is less than the current value. This works because when you do an in-order traversal on a BST, the elements must be strictly in increasing order. This method also runs in O(N) time and O(1) space.

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
  if (!p) return true;
  return (isBSTInOrderHelper(p->left, prev) && 
          (p->data > prev) && (prev = p->data) && 
          isBSTInOrderHelper(p->right, prev));
}

bool isBSTInOrder(BinaryTree *root) {
  int prev = INT_MIN;
  return isBSTInOrderHelper(root, prev);
}

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {

if (!p) return true;

return (isBSTInOrderHelper(p->left, prev) &&

(p->data > prev) && (prev = p->data) &&

isBSTInOrderHelper(p->right, prev));

}

bool isBSTInOrder(BinaryTree *root) {

int prev = INT_MIN;

return isBSTInOrderHelper(root, prev);

}

EDIT: (Bug fix)
An id han6 from the MITBBS forum pointed that the above code has a bug. When one of the node’s value is 0, the function would return false straight away, even though it is a valid BST. Why?

Below is the corrected code:

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
  if (!p) return true;
  if (isBSTInOrderHelper(p->left, prev)) {
    if (p->data > prev) {
      prev = p->data;
      return isBSTInOrderHelper(p->right, prev);
    } else {
      return false;
    }
  }
  else {
    return false;
  }
}

bool isBSTInOrderHelper(BinaryTree *p, int& prev) {

if (!p) return true;

if (isBSTInOrderHelper(p->left, prev)) {

if (p->data > prev) {

prev = p->data;

return isBSTInOrderHelper(p->right, prev);

} else {

return false;

}

else {

return false;

}

Additional Exercise:
We know that the brute force solution is inefficient. But how does it compare to the better solutions? In other words, what is the run time complexity of the brute force solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?

(Hint: The run time complexity for the brute force approach is NOT exponential.)

Rating: 4.3/5 (3 votes cast)

Determine if a Binary Tree is a Binary Search Tree (BST), 4.3 out of 5 based on 3 ratings

← Detecting a Loop in a Singly Linked List

Printing a Binary Tree in Level Order →

27 responses to Determine if a Binary Tree is a Binary Search Tree (BST)

Prateek said on October 2, 2010
This has another popular part of finding the largest BST inside a binary tree.
For that, the range solution will need slight modification.
VA:F [1.9.22_1171]
0
Reply
1337c0d3r said on October 3, 2010
I haven't heard of the question of finding the largest BST inside a binary tree, but now I know it, thanks to you.
Thanks Prateek again for your comment.
VA:F [1.9.22_1171]
0
Reply
xitrium said on November 30, 2010
Doesn't the alternative solution fail for something like this:
2
/ \
3 4
? It seems to me like it would compare 3 vs. INT_MIN and leave it at that.
VA:F [1.9.22_1171]
0
Reply
- Chen Xie said on January 3, 2013
  I believe you are right. Its because the local ‘cur’ value is not ‘propagated’ up in the recursion stack
  VN:F [1.9.22_1171]
  0
  Reply
Zhe said on March 11, 2011
a little doubt about the in-order traverse solution.
what if (prev = p->data) returns 0, it will return false.
bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
if (!p) return true;
return (isBSTInOrderHelper(p->left, prev) &&
(p->data > prev) && (prev = p->data) &&
isBSTInOrderHelper(p->right, prev));
VA:F [1.9.22_1171]
0
Reply
- 1337c0d3r said on March 11, 2011
  You are right. The in-order traverse solution has a bug in it. Please read the “Edit” section after the “Alternative solution”. I had mentioned about the bug fix.
  VN:F [1.9.22_1171]
  0
  Reply
bwzhou said on March 18, 2011
the complexity of brute-force solution is O(nlogn)? because each node is traversed once by each of its ancestors and the number of ancestors is O(logn).
VA:F [1.9.22_1171]
0
Reply
Sachin Midha said on March 19, 2011
I suppose the complexity of brute force solution n*n in the worst case.
Explanation:
Suppose the BST is in the form of a linear list,i.e, all elements inserted in a sorted order(all left pointers will be NULL), then for each node, we compare its value with all of the node on the right and we get a count as
n-1 — for the first node
n-2 — for the second node
.
.
1 — for the pen-ultimate node
0 — for the last node
i.e. (n-1) + (n-2) + (n-3) + … + 2 + 1 = n*(n-1)/2 ====== O(n^2).
Please correct me if i am wrong…
VA:F [1.9.22_1171]
0
Reply
Alias said on May 3, 2011
A little doubt about the improved “bool isBSTHelper(BinaryTree *p, int low, int high)”:
when calling the following,
bool isBST(BinaryTree *root) {
// INT_MIN and INT_MAX are defined in C++’s library
return isBSTHelper(root, INT_MIN, INT_MAX);
}
MIN and MAX are never updated in the code when encounting a left->right subtree or a right->left subtree, therefore the relevant constraint information is never passed down appropriately.
VA:F [1.9.22_1171]
0
Reply
Alias said on May 3, 2011
Example:
N1:17
/ \
N2: 8 N3: 25
/ \
N4: 5 N5: 18
according to the algorithm, here are the steps:
isBSTHelper(N1, MIN, MAX)
( MIN < 17 true
return isBSTHelper(N2, MIN, 17)
&& isBSTHelper(N3, 17, MAX)
following
(MIN < 8 true
return isBSTHelper(N4, min, 8)
&& isBSTHelper(N5, 8, MAX)
The problem is at step , which evaluates as ( 8<18 true, where it should be false because 18 > 17. Since MAX is never updated – && isBSTHelper(N5, 8, 18) — the algorithm fails at step .
VA:F [1.9.22_1171]
0
Reply
Alias said on May 3, 2011
Uh! Misunderstanding on my side. Ignore or delete my comments.
VA:F [1.9.22_1171]
0
Reply
Chetan Sharma said on May 22, 2011
Another solutions to this problem which I thought was to get the maximum value node in the root node’s left sub-tree and minimum value node in root’s right sub-tree and compare then with the root; if the root->val is greater than the maximum value in its left sub-tree but less than that of the minimum value in it’s right sub-tree then it is a Binary Search Tree otherwise not!!
VA:F [1.9.22_1171]
0
Reply
- daxingqiao said on June 18, 2011
  Yeah, I have also thought the same solution
  VA:F [1.9.22_1171]
  0
  Reply
  - maxq said on July 6, 2011
    I also thought the same idea, but after code it on the paper, I found 1337coder’s code
    is much cleaner.
    VA:F [1.9.22_1171]
    0
    Reply
maxq said on July 6, 2011
For the alternative solution, the in-order traversal one, to me it seems
the non-recusive version seems more straight forward, aka implement
a function to get the next node in in-order traversal and call the function
in a loop, that way we don’t need to pass by reference. On the coding
side it would be a bit more complicated though.
VA:F [1.9.22_1171]
0
Reply
- moonus said on September 15, 2011
  There are several ways to do in-order without recursion. I would agree with you on this. With a while/for loop, we can easily express and understand the solution.
  VA:F [1.9.22_1171]
  0
  Reply
Karl said on September 14, 2011
How about do it recursively
bool IsBST(Node* root)
{
if (!root) return true;
bool check_left = root->left ? root->value > root->left->value : true;
bool check_right = root->right? root->value right->value : true;
return check_left && check_right &&
IsBST(root->left) && IsBST(root->right);
}
VA:F [1.9.22_1171]
0
Reply
- Karl said on September 14, 2011
  No. This is not correct.
  VA:F [1.9.22_1171]
  0
  Reply
Ratna said on November 9, 2011
Inorder traversal can help in this problem, since, we will get an ascending order of elements only if it is a BST.
But, we got to use a global variable in the recursive call.
int x = INT_MIN; //global variable
bool isBST(node *root)
{
bool a,b,c;
if(!root)
return true;
a = isBST(root -> left);
if(x data)
{
x = root -> data;
c = true;
} else {
c = false;
}
b = isBST(root -> right);
return a&&b&&c;
}
VN:F [1.9.22_1171]
0
Reply
capcase said on December 5, 2011
another approach is bottom up. the advance is that mix, max is derived from bottom, because sometimes the node value is not integer and you don’t know the min, max value.
bool isBST (BinaryTree *p, int &min, int &max) {
if (!p) return true;
bool left = true;
bool right = true;
if (p->left == null)
min = p->data;
else
left = isBST(p->left, min, max);
if (p->right == null)
max = p->data;
else
right = isBST(p->right, min, max);
if (!left || !right)
return false;
if (p->data data > max)
return false;
return true;
}
bool isBST (BinaryTree *root) {
int min, max;
return isBST(root, min, max);
}
VA:F [1.9.22_1171]
0
Reply

capcase said on December 5, 2011

bool isBST (BinaryTree *p, int &min, int &max) {
  if (!p) return true;

  bool left = false;
  bool right = false;
 
  if (p->left == null) 
      min = p->data;
    else 
      left = isBST(p->left, min, max);

  if (p->right == null) 
      max = p->data;
    else 
      right = isBST(p->right, min, max);

if (!left || !right) 
  return false;
  
if (p->data  data > max) 
  return false;

return true;
}
 
bool isBST (BinaryTree *root) {
  int min, max;
  return isBST(root, min, max);
}

bool isBST (BinaryTree *p, int &min, int &max) {

if (!p) return true;

bool left = false;

bool right = false;

if (p->left == null)

min = p->data;

else

left = isBST(p->left, min, max);

if (p->right == null)

max = p->data;

else

right = isBST(p->right, min, max);

if (!left || !right)

return false;

if (p->data data > max)

return false;

return true;

}

bool isBST (BinaryTree *root) {

int min, max;

return isBST(root, min, max);

}

Karthikeyan.M said on June 11, 2012
is there any bug in the following implementation ??
bool isBST(node* root,int min,int max)
{
if(!root)return true;
int x=root->data;
if(x > min && xlft,min,x-1) && isBST(root->ryt,x+1,max))
return true;
else
return false;
}
call with isBST(root,INT_MIT,INT_MAX)
VN:F [1.9.22_1171]
0
Reply
Eugene said on June 20, 2012
I don’t see the recursive version has much connection with the analysis before, it’s just recursively compare node with its left/right child, definitely it’s the right answer…
VN:F [1.9.22_1171]
0
Reply
fenghaolw said on October 3, 2012
I think the complexity of brute-force solution is O(nlogn)
the root need to check n – 1 nodes
two children of root: each one only need to check (n-1)/2 -1 in the worst case, so in total n – 3
then the next level at most 4*[(n-3)/4 - 1] = n – 7
so in the k-th level we need to check n – (2^k – 1) nodes in the worst case
the height of BST is logn
so in total
sum^logn_1 n – (2^k – 1) = n logn – 2(n – 1) + log n = O(nlogn)
VA:F [1.9.22_1171]
0
Reply
Partha Pratim Sirker said on February 24, 2013
Here is complete java code for checking whether a binary tree is bet
http://www.dsalgo.com/2013/02/CheckForBST.php.html
here all the nodes are passed a range, like root can be from -inf to + inf. now root left can be -inf to root.value, root right can be root.value to +inf. this way this recursive function drills down by preorder traversal and checks all the nodes by their range as set by its parent.
VA:F [1.9.22_1171]
0
Reply
swapnil Kate said on March 17, 2013
As per your code you have written the running time of both of your code is O(N). But can we say it is O(height) where height of a tree can take any value between N to logN where N is the number of nodes in the tree.
VA:F [1.9.22_1171]
0
Reply
diane said on April 10, 2013
what is the run time complexity of the brute force solution? I guess it is O(n^2). I would like to know the correct answer.
VN:F [1.9.22_1171]
0
Reply