98. Validate Binary Search Tree

Inorder Traversal Version I

In this solution, we store the inorder traversal sequence, then check if it is sorted. (If a tree is a binary search tree, the inorder traversal sequence must be sorted).

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private void helper(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        helper(root.left, list);
        list.add(root.val);
        helper(root.right, list);
    }

    private boolean isSorted(List<Integer> list) {
        for (int i = 0, j = 1; j < list.size(); i++, j++) {
            if (list.get(i) >= list.get(j)) {
                return false;
            }
        }
        return true;
    }

    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList();
        helper(root, list);
        return isSorted(list);
    }
}

Time complexity: O(N)

Space complexity: O(N)

Inorder Traversal Version II

In the previous solution, we traverse all the nodes, store the values, then check if the traversal sequence is sorted. The fact is, we don’t have to store all the values but only store the previous and the current, and when we meet an unsorted pair, we can return false immediately.

This version of a solution is a little bit tricky:

  • Be aware of the condition of your return, which may cause an unreachable statement problem.
  • Use a number which is smaller than Integer.MIN_VALUE to initialize prev, otherwise you will not pass some test cases.
  • Use a reference type (array or class) as the parameter in the helper method to store the previous value. If you use a primitive type, the modification inside the helper function will not work.
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private boolean helper(TreeNode root, long[] prev) {
        if (root == null) {
            return true;
        }
        if (!helper(root.left, prev)) {
            return false;
        }
        if (prev[0] >= root.val) {
            return false;
        } else {
            prev[0] = root.val;
        }
        return helper(root.right, prev);
    }

    public boolean isValidBST(TreeNode root) {
        long[] prev = {Long.MIN_VALUE};
        return helper(root, prev);
    }
}

Time Complexity: O(N)

Space Complexity: O(1)