Validate Binary Search Tree

mediumTrees: BST & Advanced61 stepsJava · Python · C++

Check that every node is strictly between the bounds set by its ancestors, not just bigger than its left child and smaller than its right child. Pass down an allowed range: going left tightens the upper bound, going right tightens the lower bound.

▶ Watch the animated trace

Traced input: root = [5, 3, 8, 1, 4, 7, 9] → true. Original problem: neetcode.io/problems/valid-binary-search-tree

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(h)

Stops at the first violation.

Key idea

A BST constraint is global: everything in the left subtree must be smaller than the node.
Carry (low, high) down the recursion.
Use long bounds so nodes equal to Integer.MIN_VALUE/MAX_VALUE still work.
An in-order traversal must be strictly increasing; that's an equivalent check.

Common mistakes

Only comparing a node with its direct children misses [5, 4, 6, null, null, 3, 7].
Using int bounds with Integer.MIN_VALUE as -∞ fails when a node is exactly MIN_VALUE.
Allowing duplicates; this problem needs strict inequality.

Solution

Java

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

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

Python

def isValidBST(root: Optional[TreeNode]) -> bool:
    return valid(root, float("-inf"), float("inf"))


def valid(node: Optional[TreeNode], low: float, high: float) -> bool:
    if not node: return True
    if not (low < node.val < high):
        return False
    return valid(node.left, low, node.val) and valid(node.right, node.val, high)

C++

bool valid(TreeNode* node, long long low, long long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) {
        return false;
    }
    return valid(node->left, low, node->val) && valid(node->right, node->val, high);
}

bool isValidBST(TreeNode* root) {
    return valid(root, LLONG_MIN, LLONG_MAX);
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Grandchild breaks the rule 3 is in the right subtree of 5 but smaller than 5.	`root = [5, 4, 6, null, null, 3, 7]`	`false`
Duplicate value Strict inequality: equal values are not allowed.	`root = [2, 2, 2]`	`false`
Integer limits long bounds make the maximum int value valid.	`root = [2147483647]`	`true`
Single node No constraints to break.	`root = [1]`	`true`