This is the blog of Will Badart.

# Simple BST Validation

02 Oct 2018

• #programming
• #c
• #hiring
• #tutorial

Today, my HackerRank problem was a bit of a blast from the past. `isBST` (i.e., write a function which determines whether a tree is a binary search tree or not) has come up on more than one interview in the past.

I remember my first time seeing this in an interview. There’s one little gotcha you might hit if you just talk it out and program according to your logic. The solution reads something like “a tree is a BST if the root is between its left and right children, and its subtrees are also BSTs.” It might look something like this:

``````bool isBST(Node* root) {
if(!root) return true;
else return root->data > root->left->data
&& root->data < root->right->data
&& isBST(root->left)
&& isBST(root->right);
}
``````

Well… not quite. Aside from the fact that this will `SEGFAULT` at leaf nodes, it also doesn’t quite capture the essence of a BST; there’s no guarantee that `root->left->right` is less than `root`. Search your feelings, you will know it to be true.

So what can we do instead? We need some way of tracking the current max and min allowed values for the current subtree, depending on its parents. When we traverse down to the left, we constrict the maximum of the subtree, and vice-versa for traversing to the right. Mine looks something like this:

``````#include <limits.h>

bool isBST(Node* root) {
return _isBST(root, INT_MIN, INT_MAX);
}

bool _isBST(Node* root, int min, int max) {
if(!root) return true;
else return root->data > min && root->data < max
&& _isBST(root->left, min, root->data)
&& _isBST(root->right, root->data, max);
}
``````

Here, I use `INT_MIN` and `INT_MAX` sort of like plus or minus infinity (many languages have constructs for this, such as `Infinity` in JavaScript and `float('inf')` in Python): the root can take any value between plus and minus infinity, so that’s the range we validate it against. As we go down, we constrict the valid range as described above.

So there’s your simple `isBST`, hope it gives a little insight into the thought process for getting a question like this on an interview.

Recent posts:

Next post: C Linked List Follow-up
Previous post: Coffee Log 25