# Is This a Binary Search Tree?

# Is This a Binary Search Tree?

mark_philosophe + 0 comments A bit of simple advice for other code travelers: checkBST does not like duplicate values;

AndreasHassing + 0 comments You should really explain how you generate the tree from input, so people can test their solutions locally as well.

vivek_23 + 0 comments Well , I just did an inorder traversal, stored them in a list and checked if they are in ascending order. If yes, then its a BST , else it isn't.

This would work for all values (signed or unsigned) a node can possess.

When compared with recursion (which has stack depth), space complexity remains the same in worst case.

Time complexity also remains O(n) , only difference being that mine is a 2-pass solution.

aluque + 0 comments To those of you having issues with simple recursive code that just checks if the children are less/greater than the current node...

Right now, as you recurse down the tree you're going to only check if the children are "valid" with respect to their parent. But consider the following tree:

3 / \ / \ 2 6 / \ / \ 1 4 5 7

You'll notice that 4 > 2 BUT 4 > 3. The number 4 should be on the right side of the tree. If you wanted it to be more like a BST it should actually look like:

3 / \ / \ / \ 2 6 / \ / \ 1 4 / \ 5 7 / 4

As a result, you'll want to make sure that on a given call of your function, you know what upstream "min" and "max" to compare against. Eg; with node "4" we know that the "max" on the left subtree is "3" (the root). The "min" is "1". Now, it might be tempting to do an in-order traversal of the tree to find the allowable min/max for each node. But it's simpler if you don't allow duplicates in your tree.

On a given node, left children must be at least 1 less than the current node. Right children must be at least 1 greater than the current node. We can start with a left-most bound of the smallest representable integer and a right-most bound of the largest representable integer.

Below is a super minimal solution that implements this concept.

#include <climits> bool checkNode(Node* n,int min,int max) { if (!n) return true; //leaf, don't disqualify if (n->data < min || n->data > max) return false; return checkNode(n->left,min,n->data -1) && checkNode(n->right,n->data+1,max); } bool checkBST(Node* root) {return checkNode(root,INT_MIN,INT_MAX);}

g_siddharth_in + 0 comments Error: Could not find or load main class Solution . Is anyone getting this continuously while submitting ?

Sort 687 Discussions, By:

Please Login in order to post a comment