4.14.11 — Validate Binary Search Tree

LeetCode 98 · Medium · ★ Blind 75

The problem

Return true if the tree is a valid binary search tree:

Every value in a node's left subtree is less than the node.
Every value in its right subtree is greater.
Both subtrees are themselves valid search trees.

The wrong answer nearly everyone gives first

Check that each node is greater than its left child and less than its right child, then recurse.

That is wrong, and here is the counterexample:

Every parent–child pair is fine: 1 < 5, 6 > 5, 4 < 6, 7 > 6. But 4 is in the right subtree of 5 and is smaller than 5, so this is not a search tree.

The rule is about whole subtrees, not about immediate children. That distinction is the entire problem, and it is why the naive check fails.

The pattern

Carry the allowed range down the tree. Every node inherits a (low, high) window from its ancestors, and passes a narrower one to each child.

Going left, the upper bound tightens to this node's value.
Going right, the lower bound tightens to this node's value.

The root starts with no bounds at all, so use infinities.

        5           range (−∞, +∞)
      /   \
     1     6        left: (−∞, 5)    right: (5, +∞)
          / \
         4   7      left: (5, 6)  ← 4 fails here

The 4 arrives with a lower bound of 5, inherited from the root, and 4 is not greater than 5. Caught.

This is the information-flows-down technique from 4.14.10, and it is the clearest example of it in the chapter.

The solution

PythonTypeScript

python

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def valid(node, low, high) -> bool:
            if not node:
                return True                    # an empty tree is valid

            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'))

function isValidBST(root: TreeNode | null): boolean {
  function valid(node: TreeNode | null, low: number, high: number): boolean {
    if (!node) return true;
    if (!(low < node.val && node.val < high)) return false;
    return valid(node.left, low, node.val)
        && valid(node.right, node.val, high);
  }

  return valid(root, -Infinity, Infinity);
}

Strict inequalities. LeetCode's definition forbids duplicates entirely. Some definitions allow equal values on one side, so ask — it changes < to <= on one branch and the interviewer is often checking whether you notice the ambiguity.

Infinities as the starting bounds remove every boundary branch, the same trick as 4.11.7. If the values could genuinely be the largest possible integer, pass None and check for it instead.

and short-circuits, so a failure in the left subtree stops the right one being walked.

The in-order solution

There is a second answer, and it is worth knowing because it says something about search trees.

An in-order traversal of a valid BST produces values in increasing order. So walk in order and check that each value is greater than the one before.

python

def isValidBST(self, root):
    self.prev = None

    def inorder(node) -> bool:
        if not node:
            return True
        if not inorder(node.left):
            return False
        if self.prev is not None and node.val <= self.prev:
            return False
        self.prev = node.val
        return inorder(node.right)

    return inorder(root)

Only the previous value is kept, not the whole list, so it is still $O(h)$ space.

Building the full list first and then checking it sorted also works, and costs $O(n)$ space. Fine as a first answer, then improve it.

Which to prefer? The range version is easier to explain and generalises to other "validate a property along the path" problems. The in-order version is a nice fact to know and is the natural one if you already think of a BST as a sorted sequence. Say both.

Complexity

$O(n)$ time, $O(h)$ space.

Where this goes next

Recover Binary Search Tree — exactly two nodes have been swapped; find them. In-order traversal, and the swapped pair shows up as the one or two places where the order breaks.
Kth Smallest Element in a BST — in-order again, stopping after k values. 4.14.12.
Largest BST Subtree — return, from each node, the size and the value range of its subtree, and whether it is a valid BST. Three values up instead of one.

The rule: the BST property is about subtrees, not children, so validate it by carrying a range downwards — or by using the fact that in-order gives you sorted output.

What the interviewer will push on

"Why is checking parent against child not enough?" Give the counterexample. This is the question the problem exists to ask, and it is the fastest way to tell who has thought about it.

"What are your starting bounds?" Infinities, so the root is unconstrained.

"Are duplicates allowed?" Ask. It changes one comparison.

"Can you do it without passing bounds?" In-order traversal, checking that values increase.

"What if the values could be the maximum integer?" Use None as the sentinel instead of infinity, and check for it.

One thing to volunteer: state the property correctly before writing anything — "every value in the left subtree, not just the left child" — and give the counterexample yourself. It shows you know where this problem's trap is.

Next: 4.14.12 Kth Smallest Element in a BST — using the sorted-order fact directly.

4.14.11 — Validate Binary Search Tree ​

The problem ​

The wrong answer nearly everyone gives first ​

The pattern ​

The solution ​

The in-order solution ​

Complexity ​

Where this goes next ​

What the interviewer will push on ​