Validate Binary Search Tree

Source

Problem

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

Assume a BST is defined as follows:

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.
A single node tree is a BST

Example

Solution

There are two solutions two this code. One solution is to use a min and max to check if the current node's value is within the valid range.

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, null, null);
}

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

Note that the min and max here are Integer instead of int. Why? Because for int there's no absolutely invalid value. If we use Integer.MIN_VALUE as the lower-bound initially, our method will return false if the root node value is equal to Integer.MINVALUE. In order to take care of that corner case, we have to use Integer and pass in null initially.

The Second solution uses in-order traversal. If you print a BST with in-order, it should be a sorted array with ascending order. Therefore, we can easily verify if the tree is a BST by comparing with previous node during a in-order traversal.

public boolean isValidBST(TreeNode root) {
    Integer n = null;
    return isValidBSTInOrder(root, Arrays.asList(n));
}

public boolean isValidBSTInOrder(TreeNode root, List<Integer> value) {
    if (root == null) return true;

    if (isValidBSTInOrder(root.left, value)) {
        Integer v = value.get(0);
        if (v == null || v < root.val) {
            value.set(0, root.val);
            return isValidBSTInOrder(root.right, value);
        }
    }
    return false;
}

The reason to use a List here is to remember the previous visited node across recursion, otherwise you could use a global variable to do the same.