Determine if a given binary tree is binary search tree.

Assumptions

• There are no duplicate keys in binary search tree.
• You can assume the keys stored in the binary search tree can not be Integer.MIN_VALUE or Integer.MAX_VALUE.

Corner Cases

• What if the binary tree is null? Return true in this case.

//思路：BST的话，每个节点的值要在范围内，所以可以recursively把value从上往下传

//time: 每一层call recursion function两次，所以2+4+8+... = O(n)

//space: 每一层是O(1)，所以是O（height） (height = logn if balanced, height = n if unbalanced)

  public boolean isBST(TreeNode root) {
    return helper(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
  private boolean helper(TreeNode root, int min, int max) {
    if (root == null) {
      return true;
    }
    if (root.key < min || root.key > max) {
      return false;
    }
    return helper(root.left, min, root.key - 1) && helper(root.right, root.key + 1, max);
  }