Validate Binary Search Tree

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

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys strictly less than the node’s key.
• The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

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:

• The number of nodes in the tree is in the range [1, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

Approach: In-order Traversal with Previous Node (Optimal Solution)

Algorithm

1. Perform an in-order traversal (left, node, right) of the tree
2. Keep track of the previously visited node prev
3. For each node, check that its value is strictly greater than prev.val
4. If the sequence is strictly ascending, the tree is a valid BST

Key Insight

In-order traversal of a BST produces a strictly increasing sequence. Checking adjacent pairs during the traversal avoids storing the whole sequence. Because the node values can span the full 32-bit range, comparing against a null prev (rather than an integer sentinel) avoids boundary issues.

Time & Space Complexity

• Time Complexity: O(n) - every node is visited once
• Space Complexity: O(n) - recursion stack in the worst case (a skewed tree)

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class ValidateBinarySearchTree {

    private TreeNode prev;

    public boolean isValidBST(TreeNode root) {
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (root == null) {
            return true;
        }
        // Check the left subtree
        if (!dfs(root.left)) {
            return false;
        }
        // Current node must be strictly greater than the previous one
        if (prev != null && prev.val >= root.val) {
            return false;
        }
        prev = root;
        // Check the right subtree
        return dfs(root.right);
    }
}

Example Walkthrough

For root = [5,1,4,null,null,3,6]:

1. Visit 1 (leftmost), prev=null → valid, prev=1
2. Visit 5, prev=1 < 5 → valid, prev=5
3. Visit 4 (right subtree of 5), prev=5 >= 4 → invalid — the value 4 in the right subtree is not strictly greater than the root 5

Alternative Approach: Range-Bounded Recursion

public class ValidateBinarySearchTreeRange {

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

    private boolean isValid(TreeNode root, long low, long high) {
        if (root == null) {
            return true;
        }
        if (root.val <= low || root.val >= high) {
            return false;
        }
        return isValid(root.left, low, root.val)
            && isValid(root.right, root.val, high);
    }
}

The range approach carries the allowed (low, high) bounds down the recursion. Using long avoids overflow when node values equal Integer.MIN_VALUE or Integer.MAX_VALUE.

Key Insights

1. Strict Inequality: Equal values in the wrong position make the tree invalid (no duplicates allowed)
2. In-order Property: A valid BST always yields a strictly ascending in-order traversal
3. Subtle Failures: Only checking child-parent relationships is insufficient — ancestors matter too
4. Single Pass: Validation happens in one traversal without storing intermediate results

The in-order traversal solution is the optimal approach, providing O(n) time and O(n) space.