98 Validate a Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

1. The left subtree of a node contains only nodes with keys less than the node's key.
2. The right subtree of a node contains only nodes with keys greater than the node's key.
3. Both the left and right subtrees must also be binary search trees.

Example 1:
    2
   / \
  1   3
Binary tree [2,1,3], return true.

Example 2:
    1
   / \
  2   3
Binary tree [1,2,3], return false.

same as CTCI 4.5 but their solution cannot pass the test of,

ex.  "[0]", and int INTEGER.MIN_VALUE/MAX_VALUE

other resource:

http://stackoverflow.com/questions/499995/how-do-you-validate-a-binary-search-tree

Solution1: In-order traversal

1. Do an in-order traversal, and copy the elements to an array
2. Check if the array is sorted

*Improved: array is unnecessary. To compare an element to its previous element, we can just track the last element we saw and compare it as we go.

However, for "some reason", it won't pass the test >< Instead, We would use traditional 'stack' approach to solve the problem as follows:

resources:

https://discuss.leetcode.com/topic/46016/learn-one-iterative-inorder-traversal-apply-it-to-multiple-tree-questions-java-solution

public static boolean isValidBST(TreeNode root){
        if(root == null)
        {
            return true;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;

        while(root != null || !stack.isEmpty())
        {
            while(root != null)
            {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if(pre != null && root.val <= pre.val)
            {
                return false;
            }
            pre = root;
            root = root.right;
        }
        return true;
    }

Solution2: Min/Max Property - left <= current <= right

Not very Time inefficient. Few notes:

1. convert MIN/MAX int to long primitive
2. the range should be [MIN-1, MAX+1] => [greaterThan, lessThan]

public boolean isValidBST(TreeNode root)
    {
        return isValidBST(root, (long)(Integer.MIN_VALUE)-1, (long)(Integer.MAX_VALUE)+1);
    }

    public boolean isValidBST(TreeNode root, long gt, long lt) {

        if(root == null)
        {
            return true;
        }

        if(root.val >= lt || root.val <= gt)
        {
            return false;
        }

        return (isValidBST(root.left, gt, root.val) && isValidBST(root.right, root.val, lt));
        }