Validate Binary Search Tree

Problem Description

Determine if a binary tree 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 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.

Examples

Constraints

• The number of nodes in the tree is in the range [1, 10⁴].
• -2³¹ ≤ Node.val ≤ 2³¹ - 1

Passing Allowed Bounds Down the Recursion Tree

A common trap is checking only if a node’s left child is smaller and its right child is larger. This is insufficient: [5, 1, 6, null, null, 4, 7] is invalid because the node 4 is in the right subtree of 5 but is smaller than 5.

Every node in the left subtree of a node X must be strictly smaller than X. Every node in the right subtree of X must be strictly larger than X. To enforce this, we must pass the valid range of values down the recursion tree.

• When traversing to the left child, update the maximum bound to the current node’s value.
• When traversing to the right child, update the minimum bound to the current node’s value.

If any node’s value falls outside its range, the tree is invalid.

Solution 1: Recursive Range Validation

Pass min and max limits down the recursion, using Long or pointers to handle boundaries near integer limits.

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

    private boolean validate(TreeNode node, Integer min, Integer max) {
        if (node == null) return true;

        // check boundaries
        if ((min != null && node.val <= min) || (max != null && node.val >= max)) {
            return false;
        }

        // left subtree must be less than node.val; right must be greater than node.val
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def validate(node, low, high):
            if not node:
                return True

            # check boundaries
            if (low is not None and node.val <= low) or (
                high is not None and node.val >= high
            ):
                return False

            # left subtree must be less than node.val; right must be greater than node.val
            return validate(node.left, low, node.val) and validate(
                node.right, node.val, high
            )

        return validate(root, None, None)

class Solution {
private:
    bool validate(TreeNode* node, TreeNode* minNode, TreeNode* maxNode) {
        if (!node) return true;

        // check boundaries
        if ((minNode && node->val <= minNode->val) || (maxNode && node->val >= maxNode->val)) {
            return false;
        }

        // left subtree must be less than node.val; right must be greater than node.val
        return validate(node->left, minNode, node) && validate(node->right, node, maxNode);
    }

public:
    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
};

Complexity Analysis:

• Time Complexity: O(n). We visit each node exactly once.
• Space Complexity: O(h) where h is the tree height, representing the recursion stack depth.

Where it breaks: If the values contain integer boundaries (-2³¹ or 2³¹ - 1), using initial bounds like Integer.MIN_VALUE or Integer.MAX_VALUE will result in false negatives because node values equal to these bounds will be incorrectly flagged as invalid. We must use null markers or pointers to represent open boundaries.

Solution 2: In-Order Traversal

An in-order traversal of a valid BST must yield values in strictly increasing order. We can perform an in-order traversal and track the previously visited node’s value.

class Solution {
    private Integer prev = null;

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

    private boolean inOrder(TreeNode node) {
        if (node == null) return true;

        if (!inOrder(node.left)) return false;

        // in-order value must be strictly greater than previous
        if (prev != null && node.val <= prev) {
            return false;
        }
        prev = node.val;

        return inOrder(node.right);
    }
}

class Solution:
    def __init__(self):
        self.prev = None

    def isValidBST(self, root: TreeNode) -> bool:
        def in_order(node):
            if not node:
                return True

            if not in_order(node.left):
                return False

            # in-order value must be strictly greater than previous
            if self.prev is not None and node.val <= self.prev:
                return False
            self.prev = node.val

            return in_order(node.right)

        return in_order(root)

class Solution {
private:
    TreeNode* prev = nullptr;

    bool inOrder(TreeNode* node) {
        if (!node) return true;

        if (!inOrder(node->left)) return false;

        // in-order value must be strictly greater than previous
        if (prev && node->val <= prev->val) {
            return false;
        }
        prev = node;

        return inOrder(node->right);
    }

public:
    bool isValidBST(TreeNode* root) {
        return inOrder(root);
    }
};

Complexity Analysis:

• Time Complexity: O(n). In-order traversal visits all nodes.
• Space Complexity: O(h) where h is the tree height.

Where it breaks: This stateful class-level property check can be problematic in parallel test suites if the object instance is reused. Keeping prev inside helper structures is cleaner.

Common Mistakes

• Only validating local parent-child relationships. Checking if left.val < parent.val < right.val fails to enforce that the entire subtrees meet the parent bounds.
• Using Integer.MIN_VALUE / Integer.MAX_VALUE as open bounds. If a tree node has a value equal to Integer.MAX_VALUE, it will fail the strict inequality check. Use null markers or pointers to represent unbounded limits.
• Using non-strict inequalities. BST nodes must be strictly ordered. Duplicate values like [1, 1] are invalid.

Frequently Asked Questions

What does in-order traversal mean? In-order traversal visits the left subtree, then the current node, then the right subtree. For any valid BST, this traversal outputs values in sorted ascending order.

Can we solve this iteratively? Yes. You can implement the in-order traversal using an explicit stack. You traverse left as far as possible, pop, check the value against prev, then move to the right child.

What does this problem test in interviews? It tests your understanding of global constraints vs local properties in binary trees, and your attention to detail regarding boundary values and strict inequalities.

← All Problems