Check if a given tree is binary search tree

http://algorithms.tutorialhorizon.com/determine-whether-given-binary-tree-is-binary-search-treebst-or-not/

Method 1 : If tree doesn’t have duplicates

• Do the inorder tra­ver­sal of the given binary tree.
• check if the pre­vi­ously vis­ited node is less than the cur­rent node value.
• If yes, then return true
• Else return false.

The above method works only when tree doesn’t have any dupli­cates

Method 2: The Max/Min Solution :

When we talk about binary search tree we talk about one prop­erty i.e leftChild.data <=root.data<rightChild, but check­ing alone this prop­erty at every node is not gonna work out.

Your root value can have any value between -∞ to + ∞. When you val­i­date the right child of 30, it can take any value between 30 and + ∞. When you val­i­date the left child of 30, it can take any value between — ∞ and 30. likewsie when you val­i­date the left child of 40, it can take any value between 30 and 40.

So the idea is Pass the min­i­mum and max­i­mum val­ues between which the node’s value must lie.

// method 1: do inOrder and check if it is in ascending order

// doesnt work in case of duplicates

public boolean isBST1(Node root) {

  if (root != null) {

    if (!isBST1(root.left))

      return false;

    if (prevNode != null && prevNode.data >= root.data) {

      return false;

    }

    prevNode = root;

    return isBST1(root.right);

  }

  return true;

}

// //method 2

// The max-Min solution

public boolean isBST2(Node root, int min, int max) {

  if (root != null) {

    if (root.data > max || root.data < min) {

      return false;

    }

    return isBST2(root.left, min, root.data)

        && isBST2(root.right, root.data, max);

  } else {

    return true;

  }

}

Integer last_printed = null;
boolean checkBST(TreeNode n) {
        if (n == null) return true;

        // Check I recurse left
        if (!checkBST(n.left)) return false;

        // Check current
        if (last_printed != null && n.data <= last_printed) {
                return false;
        }
        last_printed = n.data;

        // Check I recurse right
        if (!checkBST(n.right)) return false;

        return true;// All good!
}

We've used an Integer instead of int so that we can know when last_printed has been set to a value.
If you don't like the use of static variables, then you can tweak this code to use a wrapper class for the
integer, as shown below.
 class Wraplnt {
 public int value;
 }

boolean checkBST(TreeNode n) {
        return checkBST(n, null, null);
}

boolean checkBST(TreeNode n, Integer min, Integer max) {
        if (n == null) {
                return true;
        }
        if ((min != null && n.data <= min) I I (max != null && n.data > max)) {
                return false;
        }

        if (!checkBST(n.left, min, n.data) I I !checkBST(n.right, n.data, max)) {
                return false;
        }
        return true;
}
Check if a given tree is binary search tree - PrismoSkills
This indicates, that the test for BST should check to see that all the nodes lying left to a node should be smaller than that node and the nodes to the right of a node should all be greater than that node.

Due to the above property, every node should lie in a range defined by its closest right and left parents.

Solution 2: Another solution is to traverse the tree in In-Order.

If the tree is BST, then in-order traversal should print a sorted output.

If we store previous in-order node and compare with current node, we can have check BST

Read full article from Check if a given tree is binary search tree - PrismoSkills