check if a tree is a binary search tree

Question

I have written the following code to check if a tree is a Binary search tree. Please help me check the code:

Okay! The code is edited now. This simple solution was suggested by someone in the posts below:

IsValidBST(root,-infinity,infinity);

bool IsValidBST(BinaryNode node, int MIN, int MAX) 
{
     if(node == null)
         return true;
     if(node.element > MIN 
         && node.element < MAX
         && IsValidBST(node.left,MIN,node.element)
         && IsValidBST(node.right,node.element,MAX))
         return true;
     else 
         return false;
}

Answer 1

We do a depth-first walk through the tree, testing each node for validity as we go. A given node is valid if it's greater than all the ancestral nodes it's in the right sub-tree of and less than all the ancestral nodes it's in the left-subtree of. Instead of keeping track of each ancestor to check these inequalities, we just check the largest number it must be greater than (its lowerBound) and the smallest number it must be less than (its upperBound).

 import java.util.Stack;

final int MIN_INT = Integer.MIN_VALUE;
final int MAX_INT = Integer.MAX_VALUE;

public class NodeBounds {

BinaryTreeNode node;
int lowerBound;
int upperBound;

public NodeBounds(BinaryTreeNode node, int lowerBound, int upperBound) {
    this.node = node;
    this.lowerBound = lowerBound;
    this.upperBound = upperBound;
}
}

public boolean bstChecker(BinaryTreeNode root) {

// start at the root, with an arbitrarily low lower bound
// and an arbitrarily high upper bound
Stack<NodeBounds> stack = new Stack<NodeBounds>();
stack.push(new NodeBounds(root, MIN_INT, MAX_INT));

// depth-first traversal
while (!stack.empty()) {
    NodeBounds nb = stack.pop();
    BinaryTreeNode node = nb.node;
    int lowerBound = nb.lowerBound;
    int upperBound = nb.upperBound;

    // if this node is invalid, we return false right away
    if ((node.value < lowerBound) || (node.value > upperBound)) {
        return false;
    }

    if (node.left != null) {
        // this node must be less than the current node
        stack.push(new NodeBounds(node.left, lowerBound, node.value));
    }
    if (node.right != null) {
        // this node must be greater than the current node
        stack.push(new NodeBounds(node.right, node.value, upperBound));
    }
}

// if none of the nodes were invalid, return true
// (at this point we have checked all nodes)
return true;
}

Answer 2

UPDATE: I just saw that this solution was suggested before. Sorry about this guys, maybe somebody still finds my version useful

Here is a solution that uses In-Order Traversal to check for BST property. Before I provide the solution, I am using a definition of a BST that doesn't allow duplicates. This means that each value in the BST is unique (this is just for simplicity).

Code for recursive inorder print:

void printInorder(Node root) {
    if(root == null) {                 // base case
        return;
    }
    printInorder(root.left);           // go left
    System.out.print(root.data + " "); // process (print) data
    printInorder(root.right);          // go right
}

After this inorder traversal on a BST, all the data should be printed in sorted ascending order. For example the tree:

   5
 3   7
1 2 6 9

would have inorder print:

1 2 3 5 6 7 9

Now, instead of printing the node, we can keep track of the previous value in the In-Order sequence and compare it to the current node's value. If the current node's value is smaller than the previous value, this means that the sequence isn't in the ascending sorted order and that the BST property is violated.

For example, the tree:

   5
 3   7
1 8 6 9

Has a violation. The right child of 3 is 8 and this would be ok if 3 was the root node. However, in a BST 8 would end up as a left child of 9 and not as a right child of 3. Therefore, this tree is not a BST. So, the code that follow this idea:

/* wrapper that keeps track of the previous value */
class PrevWrapper {
    int data = Integer.MIN_VALUE;
}

boolean isBST(Node root, PrevWrapper prev) {
    /* base case: we reached null*/
    if (root == null) {
        return true;
    }

    if(!isBST(root.left, prev)) {
        return false;
    }
    /* If previous in-order node's data is larger than
     * current node's data, BST property is violated */
    if (prev.data > root.data) {
        return false;
    }

    /* set the previous in-order data to the current node's data*/
    prev.data = root.data;

    return isBST(root.right, prev);
}

boolean isBST(Node root) {
    return isBST(root, new PrevWrapper());
}

The in-order traversal for the sample tree would fail the check for node 5 since previous in-order of 5 is 8, which is larger so BST property is violated.

Answer 3

A binary search tree has the following properties where the key for the left node must be <= the root node key and the right node key must be greater that the root.

So the problem we have is if the keys in the tree are not unique and a in order traversal was done we could get a situation of two in order traversals producing the same sequence, where 1 would be a valid bst and the other would not, this would happen if we had a tree where the left node = root(valid bst) and the right node = root(invalid not a bst).

To get around this we need to maintain a valid min/max range that the key being 'visited' must fall between, and we pass this range as we recurse to other nodes.

#include <limits>

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

The calling function will pass the above min and max values initially to isBst(...)

bool isBst(node* root, int min, int max)
{
    //base case
    if(root == NULL)
        return true;

    if(root->val <= max && root->val >= min)
    {
        bool b1 = isBst(root->left, min, root->val);
        bool b2 = isBst(root->right, root->val, max);
        if(!b1 || !b2)
            return false;
        return true;
    }
    return false;
}

Answer 4

boolean bst = isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);

public boolean isBST(Node root, int min, int max) {
    if(root == null) 
        return true;

    return (root.data > min &&
            root.data < max &&
            isBST(root.left, min, root.data) &&
            isBST(root.right, root.data, max));
    }

Answer 5

public void inorder()
     {
         min=min(root);
         //System.out.println(min);
         inorder(root);

     }

     private int min(BSTNode r)
         {

             while (r.left != null)
             {
                r=r.left;
             }
          return r.data;


     }


     private void inorder(BSTNode r)
     {

         if (r != null)
         {
             inorder(r.getLeft());
             System.out.println(r.getData());
             if(min<=r.getData())
             {
                 System.out.println(min+"<="+r.getData());
                 min=r.getData();
             }
             else
             System.out.println("nananan");
             //System.out.print(r.getData() +" ");
             inorder(r.getRight());
             return;
         }
     }

Answer 6

    boolean isBST(TreeNode root, int max, int min) {
        if (root == null) {
            return true;
        } else if (root.val >= max || root.val <= min) {
            return false;
        } else {
            return isBST(root.left, root.val, min) && isBST(root.right, max, root.val);
        }

    }

an alternative way solving this problem.. similar with your code

Answer 7

right, another simple solution is do an inorder visit

java code here

Answer 8

A Method should only do one thing at a time. Also the way you do things are generally Weird. I will give you some almost-Java pseudocode. Sorry for that, but I have not touched Java for some Time. I hope it helps. Look at the comments I also did on the Question and I hope you sort it out!

Call your isBST like that :

public boolean isBst(BNode node)
{
    return isBinarySearchTree(node , Integer.MIN_VALUE , Integer.MIN_VALUE);
}

Internally :

public boolean isBinarySearchTree(BNode node , int min , int max)
{
    if(node.data < min || node.data > max)
        return false;
    //Check this node!
    //This algorithm doesn't recurse with null Arguments.
    //When a null is found the method returns true;
    //Look and you will find out.
    /*
     * Checking for Left SubTree
     */
    boolean leftIsBst = false;
    //If the Left Node Exists
    if(node.left != null)
    {
        //and the Left Data are Smaller than the Node Data
        if(node.left.data < node.data)
        {
            //Check if the subtree is Valid as well
            leftIsBst = isBinarySearchTree(node.left , min , node.data);
        }else
        {
            //Else if the Left data are Bigger return false;
            leftIsBst = false;
        }
    }else //if the Left Node Doesn't Exist return true;
    {
        leftIsBst = true;
    }

    /*
     * Checking for Right SubTree - Similar Logic
     */
    boolean rightIsBst = false;
    //If the Right Node Exists
    if(node.right != null)
    {
        //and the Right Data are Bigger (or Equal) than the Node Data
        if(node.right.data >= node.data)
        {
            //Check if the subtree is Valid as well
            rightIsBst = isBinarySearchTree(node.right , node.data+1 , max);
        }else
        {
            //Else if the Right data are Smaller return false;
            rightIsBst = false;
        }
    }else //if the Right Node Doesn't Exist return true;
    {
        rightIsBst = true;
    }

    //if both are true then this means that subtrees are BST too
    return (leftIsBst && rightIsBst);
}

Now : If you want to find the Min and Max Values of each Subtree you should use a Container (I used an ArrayList) and store a triplet of Node, Min, Max which represents the root node and the values (obviously).

eg.

/*
 * A Class which is used when getting subTrees Values
 */
class TreeValues
{
    BNode root; //Which node those values apply for
    int Min;
    int Max;
    TreeValues(BNode _node , _min , _max)
    {
        root = _node;
        Min = _min;
        Max = _max;
    }
}

And a :

/*
 * Use this as your container to store Min and Max of the whole
 */
ArrayList<TreeValues> myValues = new ArrayList<TreeValues>;

Now this is a method which finds the Min and Max values of a given node:

/*
 * Method Used to get Values for one Subtree
 * Returns a TreeValues Object containing that (sub-)trees values
 */ 
public TreeValues GetSubTreeValues(BNode node)
{
    //Keep information on the data of the Subtree's Startnode
    //We gonna need it later
    BNode SubtreeRoot = node;

    //The Min value of a BST Tree exists in the leftmost child
    //and the Max in the RightMost child

    int MinValue = 0;

    //If there is not a Left Child
    if(node.left == null)
    {
        //The Min Value is this node's data
        MinValue = node.data;
    }else
    {
        //Get me the Leftmost Child
        while(node.left != null)
        {
            node = node.left;
        }
        MinValue = node.data;
    }
    //Reset the node to original value
    node = SubtreeRoot; //Edit - fix
    //Similarly for the Right Child.
    if(node.right == null)
    {
        MaxValue = node.data;
    }else
    {
        int MaxValue = 0;
        //Similarly
        while(node.right != null)
        {
            node = node.right;
        }
        MaxValue = node.data;
    }
    //Return the info.
    return new TreeValues(SubtreeRoot , MinValue , MaxValue);   
}

But this returns Values for one Node only, So we gonna use this to find for the Whole Tree:

public void GetTreeValues(BNode node)
{
    //Add this node to the Container with Tree Data 
    myValues.add(GetSubTreeValues(node));

    //Get Left Child Values, if it exists ...
    if(node.left != null)
        GetTreeValues(node.left);
    //Similarly.
    if(node.right != null)
        GetTreeValues(node.right);
    //Nothing is returned, we put everything to the myValues container
    return; 
}

Using this methods, your call should look like

if(isBinarySearchTree(root))
    GetTreeValues(root);
//else ... Do Something

This is almost Java. It should work with some modification and fix. Find a good OO book, it will help you. Note, that this solution could be broke down into more methods.

Answer 9

It doesn't really make much sense to return INTEGER.MIN,INTEGER.MAX as the values for an empty tree. Perhaps use an Integer and return null instead.