Validate Binary Search Tree

This is the problem where the "obvious" solution is wrong. Almost everyone's first idea is to check that each node's left child is smaller and its right child is larger. That passes most small tests and fails on a tree that looks perfectly fine locally. Interviewers use it exactly for that reason: it tests whether you read the definition carefully and whether you know which direction information must flow.

It is also the lesson where the core idea's "pass it down" arrow gets used for real. Maximum depth returned values up; here the answer depends on constraints that come from above.

The problem

Given the root of a binary tree, return True if it is a valid binary search tree (BST) and False otherwise.

valid:         8                not valid:      5             /   \                             / \            4     12                          1   6           / \   /  \                            / \          2   6 10   14                         3   7

• The left tree → True.
• The right tree → False. Node 3 is smaller than its parent 6, so every local check passes. But 3 is in the right subtree of 5, where every value must be larger than 5.

Constraints: 1 ≤ n ≤ 10⁴ nodes, values anywhere in the 32-bit signed integer range.

Clarifying questions

• Are duplicates allowed? Assume not: "strictly smaller" and "strictly larger". A tree with two 5s is invalid. (Some variants allow duplicates on one side — ask.)
• Can values be the extreme integers? Yes. This rules out using −2³¹ or 2³¹ − 1 as "no limit" markers.
• Is an empty tree valid? Yes, trivially.

Approach 1: the simple way

Check the definition literally. At every node, find the largest value in its left subtree and the smallest value in its right subtree, and compare them with the node.

1def subtree_max(node: Optional[TreeNode]) -> float:2    """Largest value in the subtree (-inf if empty)."""3    if node is None:4        return float("-inf")5    return max(node.val, subtree_max(node.left), subtree_max(node.right))678def subtree_min(node: Optional[TreeNode]) -> float:9    """Smallest value in the subtree (+inf if empty)."""10    if node is None:11        return float("inf")12    return min(node.val, subtree_min(node.left), subtree_min(node.right))131415def is_valid_bst_brute(root: Optional[TreeNode]) -> bool:16    """At every node, scan both subtrees for their max and min."""17    if root is None:18        return True19    if subtree_max(root.left) >= root.val or subtree_min(root.right) <= root.val:20        return False21    return is_valid_bst_brute(root.left) and is_valid_bst_brute(root.right)

This is correct — it catches node 3 at the root, because the minimum of 5's right subtree is 3. Note the identities: the max of an empty subtree is −∞ and the min is +∞, so a missing child never fails the check.

The cost: each node scans its whole subtree, and every node is scanned once per ancestor. That is O(n × h): O(n log n) on a balanced tree, but about n²/2 on a chain — 5 × 10⁷ steps at n = 10⁴. It also recomputes the same minima and maxima over and over.

The key insight

Look at the rule from the other side. Instead of asking each node "what is below you?", tell each node "here is the range you must fall inside" — a constraint that comes from its ancestors.

• The root can be anything: range (−∞, +∞).
• Going left from a node with value v, everything must be smaller than v. The upper bound becomes v; the lower bound is inherited.
• Going right from v, everything must be larger than v. The lower bound becomes v; the upper bound is inherited.

Each node checks itself against its range once, and passes two narrower ranges down. In the invalid tree: 6 gets (5, +∞) because it is right of 5; 3 gets (5, 6) because it is left of 6 and still right of 5. 3 is not above 5, so the tree is invalid — caught in O(1) at node 3, with no scanning.

The range is how the ancestor's constraint "every value in my right subtree is larger than 5" reaches a grandchild. The local check fails precisely because it forgets it.

Approach 2: pass the allowed range down

1def is_valid_bst(root: Optional[TreeNode]) -> bool:2    """True if every node is inside the open range its ancestors allow."""3    def check(node: Optional[TreeNode], low: float, high: float) -> bool:4        if node is None:5            return True                   # an empty subtree fits any range6        if not (low < node.val < high):7            return False8        # going left caps the values at node.val; going right floors them there9        return (check(node.left, low, node.val)10                and check(node.right, node.val, high))1112    return check(root, float("-inf"), float("inf"))

The strict < on both sides rejects duplicates. float("-inf") and float("inf") compare correctly with any Python integer, so extreme values like −2³¹ are handled; in Java, use null bounds or long values instead of Integer.MIN_VALUE.

Dry run on the invalid tree

and short-circuits, so node 7 is never checked: the answer is already False. On the valid tree every check passes — for example, 10 is checked against (8, 12) and 6 against (4, 8).

Complexity. Time is O(n): each node is checked once. Space is O(h) for the recursion.

Approach 3: inorder must be strictly increasing

The core idea lesson noted that an inorder walk of a BST visits values in sorted order. The reverse is also true: if the inorder sequence is strictly increasing, the tree is a BST. So walk inorder and compare each value with the previous one.

1def is_valid_bst_inorder(root: Optional[TreeNode]) -> bool:2    """True if an inorder walk produces strictly increasing values."""3    stack: list[TreeNode] = []4    node = root5    previous = float("-inf")6    while stack or node:7        while node:                       # go as far left as possible8            stack.append(node)9            node = node.left10        node = stack.pop()11        if node.val <= previous:          # not strictly increasing: not a BST12            return False13        previous = node.val14        node = node.right15    return True

On the invalid tree the inorder sequence is 1, 5, 3, 6, 7. At 3, the previous value is 5, so the function returns False right there. On the valid tree the sequence is 2, 4, 6, 8, 10, 12, 14.

Time is O(n) in the worst case, and it stops at the first violation. Space is O(h) for the explicit stack — and because there is no recursion, a chain of 10⁴ nodes causes no RecursionError. This version also makes the Kth Smallest follow-up a one-line change.

Edge cases

• Duplicates. A root 5 with left child 5 must be invalid. Both approaches use strict comparisons (low < val < high, val <= previous), so it is.
• Extreme values. A single node holding −2³¹ is valid. Infinity bounds handle it; an integer sentinel of −2³¹ would wrongly reject it.
• A single node or an empty tree. Both valid.
• The violation is two levels down. The lesson's invalid tree — the case the local check misses.

Saying it in the interview

Follow-ups

• "Find the k-th smallest value in a BST." Run the Approach 3 loop and return the k-th value popped. Time O(h + k), because it stops early.
• "Two nodes of a BST were swapped by mistake; fix it." Walk inorder and find where the sequence decreases. One decrease means the two adjacent values were swapped; two decreases mean the first value of the first drop and the second value of the second drop. Swap their values back.
• "Duplicates are allowed on the left." Make the left range inclusive at the top: a left child may equal its parent. In Approach 2 that means checking low < val <= high for nodes reached by going left — track which bound is inclusive.