1.5 Binary Search Tree or not

Assumption: node.key cannot be MIN or MAX_VALUE

Input: TreeNode root

Output: boolean

Corner case: if root == null, return true

Solution:

1. The subproblem is when both of the subtrees of root p is BST

2. All nodes under p > min

3. All nodes under p < max

												10 (min:-inf, max:inf)
												/			\
			5(min:-inf, max:10)		    15(min:10, max:inf)
		           /				            /		       \
	    2(min:-inf,max:5)		 12(min:10, max:15)	20(min:15, max:inf)

TC: O(# of nodes in the tree)

SC: O(height of the tree)

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