Validate Binary Search Tree

MediumTree DFSBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given the root of a binary tree. Return true if it is a valid binary search tree: for every node, every value in its left subtree is strictly less than the node's value, and every value in its right subtree is strictly greater. The rule covers whole subtrees, not just direct children, and equal values make the tree invalid. Example trees are listed row by row from the top, each row left to right, with null where a child is missing.

Examples

root = [2,1,3] returns true

1 is less than 2 and sits on the left, and 3 is greater than 2 and sits on the right. Both children are leaves, so nothing else needs checking.

root = [5,1,4,null,null,3,6] returns false

4 is in the right subtree of 5 but smaller than 5.

The root is 5, so every value in its right subtree must be greater than 5. The right child is 4, which already breaks that rule.

root = [5,4,6,null,null,3,7] returns false

3 is fine next to its parent 6 but breaks the rule for the root 5.

Each parent and child pair looks fine on its own: 3 < 6 and 7 > 6. But 3 is in the root's right subtree while being less than 5, so the tree is invalid.

Constraints

1 <= number of nodes <= 10^4

Hints

Hint 1

Comparing a node only to its immediate parent isn't enough, what would you need to carry down the recursion?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Recurse while carrying the open range (lo, hi) that the current node's value must fall strictly inside, starting with no bounds at the root. Going left, the node's value becomes the new upper bound; going right, it becomes the new lower bound. That way every node is checked against all of its ancestors, not just its parent, and any value on or outside a bound fails at once. O(n) time, O(h) stack space.

Time

O(n)

Space

O(h)

Pitfall

Checking each node only against its direct children, which accepts [5,4,6,null,null,3,7] even though 3 sits in the right subtree of 5. Use null for a missing bound, not Integer.MIN_VALUE or MAX_VALUE, since nodes can hold those values.

Solutions

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

    private boolean validate(TreeNode node, Integer lo, Integer hi) {
        if (node == null) return true;
        if (lo != null && node.val <= lo) return false;
        if (hi != null && node.val >= hi) return false;
        return validate(node.left, lo, node.val)
            && validate(node.right, node.val, hi);
    }
}

class Solution:
    def isValidBST(self, root) -> bool:
        def validate(node, lo, hi):
            if not node:
                return True
            if lo is not None and node.val <= lo:
                return False
            if hi is not None and node.val >= hi:
                return False
            return (validate(node.left, lo, node.val)
                    and validate(node.right, node.val, hi))
        return validate(root, None, None)