Careful with BST

Validate Binary Search Tree: http://lintcode.com/en/problem/validate-binary-search-tree/#

Error1: {2147483647} corner case

Error2: we need to use return new Result(Math.min(left.min, root.val), Math.max(right.max, root.val), true) instead of the Wrong one.

public boolean isValidBST(TreeNode root) {
    // write your code here
    Result res = helper(root);
    return res.isBST;
}

private Result helper(TreeNode root){
    if(root == null){
        return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, true);
    }

    Result left = helper(root.left);
    Result right = helper(root.right);

    if(left.isBST && right.isBST){
        if(root.val > left.max && root.val < right.min){
            return new Result(left.min, right.max, true); // Wrong!!!
        }else{
            return new Result(-1, -1, false);    
        }
    }

    return new Result(-1, -1, false);
}

The above code is wrong because if we use Integer.MAX_VALUE and Integer.MIN_VALUE as min and max of null node,

we cannont deal with corner case {2147483647}.

Solution1: use Long instead of Integer

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    class Result{
        long min, max;
        boolean isBST;

        public Result(long min, long max, boolean isBST){
            this.min = min;
            this.max = max;
            this.isBST = isBST;
        }
    }

    public boolean isValidBST(TreeNode root) {
        // write your code here
        Result res = helper(root);
        return res.isBST;
    }

    private Result helper(TreeNode root){
        if(root == null){
            return new Result(Long.MAX_VALUE, Long.MIN_VALUE, true);
        }

        Result left = helper(root.left);
        Result right = helper(root.right);

        if(left.isBST && right.isBST){
            if(root.val > left.max && root.val < right.min){
                return new Result(Math.min(left.min, root.val), Math.max(right.max, root.val), true);
            }else{
                return new Result(-1, -1, false);    
            }
        }

        return new Result(-1, -1, false);
    }
}

Solution2: check if the left node and right node is null first then check BST

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
class ResultType {
    boolean is_bst;
    int maxValue, minValue;

    ResultType(boolean is_bst, int maxValue, int minValue) {
        this.is_bst = is_bst;
        this.maxValue = maxValue;
        this.minValue = minValue;
    }
}

public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: True if the binary tree is BST, or false
     */
    public boolean isValidBST(TreeNode root) {
        ResultType r = validateHelper(root);
        return r.is_bst;
    }

    private ResultType validateHelper(TreeNode root) {
        if (root == null) {
            return new ResultType(true, Integer.MIN_VALUE, Integer.MAX_VALUE);
        }

        ResultType left = validateHelper(root.left);
        ResultType right = validateHelper(root.right);

        if (!left.is_bst || !right.is_bst) {
            // if is_bst is false then minValue and maxValue are useless
            return new ResultType(false, 0, 0);
        }

        if (root.left != null && left.maxValue >= root.val || 
              root.right != null && right.minValue <= root.val) {
            return new ResultType(false, 0, 0);
        }

        return new ResultType(true,
                              Math.max(root.val, right.maxValue),
                              Math.min(root.val, left.minValue));
    }
}

Similar question:

Largest BST Subtree: https://leetcode.com/problems/largest-bst-subtree/#/description