Generated by Codex with GPT-5

Quick facts

Problem gist

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

The important detail is that the BST rule is global, not just local. A node in the left subtree must be smaller than the root, not merely smaller than its parent. A node in the right subtree must be larger than the root, not merely larger than its parent. The same rule repeats at every node.

For example, this is invalid even though each immediate child may look reasonable:

    5
   / \
  1   7
     /
    4

The node 4 is in the right subtree of 5, so it must be greater than 5. It is not, so the whole tree fails.

Core idea

Carry a valid value range as the traversal moves down the tree.

At the root, there is no lower or upper bound. When moving left from a node with value x, every node in that left subtree must be less than x, so x becomes the upper bound. When moving right, every node in that right subtree must be greater than x, so x becomes the lower bound.

Each node is valid only if:

  1. It is greater than the lower bound, when one exists.
  2. It is less than the upper bound, when one exists.
  3. Its left and right subtrees are valid under their updated bounds.

Using None for missing bounds avoids awkward sentinel values. This matters because node values can be near the edge of the allowed integer range, and a fake -infinity or infinity can invite avoidable mistakes.

Python solution

from typing import Optional


# LeetCode provides TreeNode. The shape is shown here for clarity:
# class TreeNode:
#     def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    def isValidBST(self, root: Optional["TreeNode"]) -> bool:
        return self._is_within_bounds(root, lower_bound=None, upper_bound=None)

    def _is_within_bounds(
        self,
        node: Optional["TreeNode"],
        lower_bound: Optional[int],
        upper_bound: Optional[int],
    ) -> bool:
        if node is None:
            return True

        if lower_bound is not None and node.val <= lower_bound:
            return False

        if upper_bound is not None and node.val >= upper_bound:
            return False

        # Left descendants must stay below this node; right descendants must stay above it.
        return (
            self._is_within_bounds(node.left, lower_bound, node.val)
            and self._is_within_bounds(node.right, node.val, upper_bound)
        )

Why it works

Every node in a BST has two inherited promises: all ancestors that placed it in a right subtree give it a lower bound, and all ancestors that placed it in a left subtree give it an upper bound.

The recursive helper stores exactly those promises. If a node breaks either bound, there is no way for its subtree to be a valid BST, so the algorithm returns False. If the node fits, the helper tightens the range before visiting each child.

This checks the full ancestor path, not only the parent-child relationship. Because every node is visited once under the exact range it must satisfy, passing all checks is both necessary and sufficient for the tree to be a valid BST.

Complexity

Let n be the number of nodes and h be the height of the tree.

The runtime is O(n) because each node is checked once. The extra space is O(h) for the recursion stack. In a balanced tree, h = O(log n). In a completely skewed tree, h = O(n).

Interview follow-ups

Why is checking only each node against its children incorrect?

That local check misses violations caused by ancestors. A node can be greater than its immediate parent but still too small for a higher ancestor, or smaller than its immediate parent but still too large for a higher ancestor.

The expected fix is to carry bounds from the full ancestor chain. This works because every left or right turn narrows the set of values allowed below that point. The complexity remains O(n) time, and the stack space remains O(h).

Can this be solved with inorder traversal?

Yes. An inorder traversal of a valid BST visits values in strictly increasing order. The algorithm keeps the previous visited value and returns False if the current value is less than or equal to it.

This works because inorder visits the entire left subtree, then the node, then the right subtree. In a BST, every left value must be smaller than the node and every right value must be larger, so the resulting sequence must be sorted with no duplicates. It has the same O(n) time complexity and O(h) recursion or stack space.

The bounds method is often easier to explain for ancestor-based violations. The inorder method is compact and especially natural when the interviewer asks for the sorted-order property of BSTs.

How would you avoid recursion depth issues?

Use an explicit stack. Each stack entry stores a node plus its current lower and upper bounds. Pop an entry, validate the node, then push its right and left children with updated bounds.

This has the same asymptotic cost as recursion: O(n) time and O(h) space. The tradeoff is implementation style. The iterative version is a little more verbose, but it avoids Python’s recursion limit on a very deep skewed tree.

What if duplicate values are allowed?

First clarify the rule. Some BST definitions allow duplicates on the left, some allow duplicates on the right, and many interview versions do not allow duplicates at all.

The solution changes only in the comparison operators. If duplicates may go left, the left subtree can use an inclusive upper bound while the right subtree keeps a strict lower bound. If duplicates may go right, the opposite applies. The key is to make the inclusivity consistent across the whole tree; otherwise a duplicate can slip through in the wrong subtree.

How would you return the first invalid node instead of a boolean?

Keep the same bounds traversal, but return the offending node or value when a bound check fails. If the current node is valid, recursively search the left subtree first, then the right subtree, and return the first non-null violation found.

This still works because the bounds already encode exactly why a node is invalid. The runtime is O(k) if a violation is found after visiting k nodes, or O(n) if the tree is valid. Space remains O(h).