Validate Binary Search Tree (LeetCode 98)

The problem

You get the root of a binary tree. Return True if it is a valid binary search tree:

• every value in a node’s left subtree is strictly less than the node,
• every value in its right subtree is strictly greater,
• and both subtrees are themselves valid BSTs.

Input:  [5, 1, 4, null, null, 3, 6]

        5
       / \
      1   4
         / \
        3   6

Output: False

4 is in 5’s right subtree, so it must be greater than 5. It isn’t.

A sneakier failure: [5, 4, 6, null, null, 3, 7]. Node 3 is a correct left child of 6, but it’s in 5’s right subtree, so it must be greater than 5.

How to think about it

Start with the tempting wrong answer. Check that each node’s left child is smaller and its right child is larger. That passes the second example above, which is not a BST. The rule is about whole subtrees, not just direct children. A node deep down must respect every ancestor it sits under.

The honest brute force: for each node, scan its whole left subtree for the maximum and its right subtree for the minimum. That’s correct, but O(n²) on a skewed tree.

The key insight: each node lives inside a range set by its ancestors. The root can be anything: (-∞, +∞). Going left from a node with value v, everything below must be < v, so the upper bound becomes v. Going right, the lower bound becomes v. So pass (lo, hi) down, check lo < node.val < hi, and tighten one side at each step. One pass, O(n).

Which pattern is this? Tree DFS with state flowing down. The tell is “valid BST”: a rule that every node must satisfy relative to all its ancestors.

Approach

1. Call valid(root, -inf, +inf).
2. An empty node is valid.
3. If the node’s value is not strictly between lo and hi, return False.
4. Check the left subtree with range (lo, node.val) and the right subtree with (node.val, hi).
5. The tree is valid only if both are.

Solution

def is_valid_bst(root):
    def valid(node, lo, hi):
        if not node: return True
        if not (lo < node.val < hi): return False                  # must sit inside the range from its ancestors
        return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)   # tighten one side
    return valid(root, float('-inf'), float('inf'))
# is_valid_bst(tree[2,1,3]) -> True ; is_valid_bst(tree[5,1,4,null,null,3,6]) -> False

Dry run

On the sneaky case [5, 4, 6, null, null, 3, 7]:

A child-only check would have accepted node 3. The range catches it because it remembers the bound from 5.

Complexity

• Time: O(n). Each node is checked once, and the check is O(1).
• Space: O(h). The recursion stack is as deep as the tree height: O(log n) balanced, O(n) skewed.

Edge cases and pitfalls

• Empty tree is a valid BST.
• Duplicates are invalid under strict inequality: [2, 2, 2] returns False. Confirm the rule with your interviewer; some variants allow equal values on one side.
• Extreme values. If you use INT_MIN/INT_MAX as sentinels, a node holding exactly that value fails. Infinity (or None for “no bound”) avoids it.
• Alternative: an in-order traversal of a valid BST is strictly increasing. Track the previous value and fail on any non-increase. Same O(n).

Related problems

• Kth Smallest Element in a BST (LeetCode 230): uses the sorted in-order property this check protects.
• Lowest Common Ancestor of a BST (LeetCode 235): relies on the same ordering to choose a side.
• Path Sum (LeetCode 112): another DFS that passes state down to each child.