Validate Binary Search Tree

Share

Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST).

A valid BST is defined as:

Example 1
Input: root = [2,1,3]
Output: true
Example 2
Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
Constraints:

Contents

Approach 1: Inorder Traversal

Inorder traversal of a BST produces a strictly increasing sequence. Collect all values inorder and verify each is greater than the previous.

Java
public boolean isValidBST(TreeNode root) {
    List<Integer> inorder = new ArrayList<>();
    inorderCollect(root, inorder);

    for (int i = 1; i < inorder.size(); i++) {
        if (inorder.get(i) <= inorder.get(i - 1)) return false;
    }
    return true;
}

private void inorderCollect(TreeNode node, List<Integer> list) {
    if (node == null) return;
    inorderCollect(node.left, list);
    list.add(node.val);
    inorderCollect(node.right, list);
}
Complexity:

Approach 2: Min/Max Range (Optimal, O(1) extra space)

Pass a valid range [min, max] down the recursion. At each node, verify its value is strictly within the range; update the bounds for subtrees.

Java
public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.val <= min || node.val >= max) return false;

    return validate(node.left,  min, node.val)    // left subtree: max = node.val
        && validate(node.right, node.val, max);   // right subtree: min = node.val
}
Use Long.MIN_VALUE / Long.MAX_VALUE (not Integer) as initial bounds to handle nodes with values equal to Integer.MIN_VALUE or Integer.MAX_VALUE.

Complexity Analysis
ApproachTimeSpace
Inorder traversalO(n)O(n): list storage
Min/Max rangeO(n)O(h): call stack only