LeetCode 98 – Validate Binary Search Tree

Validate Binary Search Tree has the most famous wrong answer on the list. The natural check — every node is greater than its left child and less than its right child — is not the BST property, it is a much weaker local version of it, and it accepts trees that are plainly not search trees. The problem exists to see whether you notice.

The problem

Given the root of a binary tree, decide whether it is a valid binary search tree:

Every node in the entire left subtree is strictly less than the node.
Every node in the entire right subtree is strictly greater.
Both subtrees are themselves valid BSTs.

    2
   / \      -> true
  1   3

    5
   / \      -> false
  1   4     4 < 5, so it cannot be in the right subtree
     / \
    3   6

    5
   / \      -> false  -- the one the naive check gets wrong
  1   6
     / \
    4   7

  4 is 6's left child and 4 < 6, so that pair is fine.
  1 < 5 < 6, so those pairs are fine too. EVERY parent-child pair passes.
  But 4 sits in 5's right subtree and 4 < 5, so the tree is not a BST.

That third tree is the counterexample to have ready. Check each node against its immediate children and every single pair passes. The tree is still invalid, because 4 sits somewhere in the right subtree of 5 while being smaller than 5.

The word doing the work is "entire"

The constraint on a node is not set by its parent. It is set by every ancestor, and it narrows as you descend:

           5            range (-inf, +inf)
          / \
   (-inf,5)  (5,+inf)
        1      6
              / \
        (5,6)     (6,+inf)
          4          7      <- 4 must be in (5,6). It is not. Invalid.

Going left tightens the upper bound to the current node's value; going right tightens the lower bound. Carry both down the recursion and the check becomes local again — but against the right bounds this time.

The sentinel trap

Starting the bounds at Integer.MIN_VALUE and Integer.MAX_VALUE is the obvious move and it fails on a single-node tree whose value is Integer.MIN_VALUE: that node is not strictly greater than the lower bound, so a perfectly valid tree is rejected.

Two clean fixes. Use long bounds, since node values are ints and cannot reach Long.MIN_VALUE. Or use nullable Integer bounds where null means unbounded, which says what you mean and survives even if the values become longs later. The version below uses Integer for that reason.

Java

class Solution {
    public boolean isValidBST(TreeNode root) {
        return valid(root, null, null);      // null bounds = unbounded
    }

    /** Every value in this subtree must lie strictly between low and high. */
    private boolean valid(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;       // an empty tree is a valid BST

        if (low != null && node.val <= low) return false;
        if (high != null && node.val >= high) return false;

        // Going left caps the values from above; going right raises the floor.
        return valid(node.left, low, node.val)
            && valid(node.right, node.val, high);
    }
}

<= and >=, not < and >. The inequalities are strict, so duplicate values are invalid — a tree with two 5s is rejected. Ask which convention the interviewer wants: some definitions allow duplicates on one side, and the answer changes one character. Asking beats guessing.

Note that node.val is passed as both the new upper bound for the left and the new lower bound for the right, which is exactly the picture above translated into code.

Python

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        def valid(node, low, high) -> bool:
            if node is None:
                return True
            if not (low < node.val < high):
                return False
            return valid(node.left, low, node.val) and valid(node.right, node.val, high)

        return valid(root, float("-inf"), float("inf"))

low < node.val < high is the constraint written as the mathematical statement it is, and float("-inf") genuinely has no representable integer below it, so the sentinel problem that bites in Java does not exist here. Comparing an int to a float infinity is exact in Python — no precision is lost, because infinity is not a nearby float.

The inorder alternative

From problem 94: inorder traversal of a BST produces sorted output. So a tree is a valid BST exactly when its inorder traversal is strictly increasing — and you only need the previous value, not the whole list:

    def isValidBSTInorder(self, root: TreeNode) -> bool:
        stack, previous = [], None
        current = root

        while current or stack:
            while current:
                stack.append(current)
                current = current.left

            current = stack.pop()
            if previous is not None and current.val <= previous:
                return False                 # not strictly increasing
            previous = current.val
            current = current.right

        return True

Same O(h) space, and it short-circuits on the first violation. It is the better answer when the follow-up is "find the two swapped nodes" (Recover Binary Search Tree, 99), because that problem is defined in terms of where the inorder sequence goes wrong.

Have both. The bounds version is easier to explain; the inorder version generalises further.

Complexity

Approach	Time	Space
Bounds recursion	`O(n)`	`O(h)` stack
Inorder with a previous value	`O(n)`	`O(h)`

Every node is visited once. O(h) is O(log n) balanced, O(n) degenerate. Both can exit early on an invalid tree, so the worst case is a valid one.

There is no sub-linear approach: a single misplaced node anywhere makes the tree invalid, so every node must be examined.

The pattern

"Pass constraints down the recursion" is the reusable move, and it appears whenever a node's validity depends on ancestors rather than neighbours. Recover Binary Search Tree (99) finds the two nodes the inorder pass reports out of order. Range Sum of BST (938) prunes subtrees whose bounds cannot contain the range. Insert / Delete in a BST (701, 450) navigate by the same narrowing.

The general lesson is broader than trees: when a local check passes but the structure is still wrong, the constraint is coming from further away than you are looking.

What the interviewer is checking

That you reject the parent-versus-children check and can produce a tree that defeats it.
That bounds come from all ancestors, narrowing on the way down.
The Integer.MIN_VALUE sentinel trap, and a fix.
Strict inequalities, and that you ask about duplicates.
Empty tree and single node.
That you know inorder on a BST is sorted, and can use it.
That O(h) stack is O(n) on a degenerate tree.