ValidBinarySearchTree.java

package tree;

/**
 * Created by gouthamvidyapradhan on 09/03/2017.
 * Given a binary tree, determine if it is a valid binary search tree (BST).
 * <p>
 * Assume a BST is defined as follows:
 * <p>
 * The left subtree of a node contains only nodes with keys less than the node's key.
 * The right subtree of a node contains only nodes with keys greater than the node's key.
 * 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.
 */
public class ValidBinarySearchTree {
    class Range {
        long low, high;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * Main method
     *
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        TreeNode root = new TreeNode(Integer.MIN_VALUE);
        root.right = new TreeNode(Integer.MAX_VALUE);
        System.out.println(new ValidBinarySearchTree().isValidBST(root));
    }

    private boolean isValidBST(TreeNode root) {
        if (root == null ||
                (root.right == null && root.left == null)) return true;
        Range range = new Range();
        range.high = Long.MAX_VALUE;
        range.low = Long.MIN_VALUE;
        return validate(root, range);
    }

    private boolean validate(TreeNode root, Range range) {
        if ((root.val > range.low) && (root.val < range.high)) {
            long temp = range.high;
            if (root.left != null) {
                range.high = root.val;
                if (!validate(root.left, range)) return false;
            }
            if (root.right != null) {
                range.high = temp;
                range.low = root.val;
                if (!validate(root.right, range)) return false;
            }
            return true;
        } else return false;
    }

}