Validate Binary Search Tree

A BST validator must remember the ancestors that still constrain the current node.

The tempting implementation checks whether each node is larger than its left child and smaller than its right child. That is only a local test. The actual rule reaches across the entire subtree, so the solution needs to carry the legal value range from the root to every descendant.

The standard Validate Binary Search Tree solution uses depth-first search with a strict lower and upper bound for each node.

Start with the exact BST contract

The input is the root of a binary tree. The output is True only if the complete tree satisfies the binary search tree rules:

• Every value in a node's left subtree is strictly smaller than the node's value.
• Every value in its right subtree is strictly greater.
• Both subtrees must satisfy the same rules.
• Duplicate values are invalid.

“Strictly” controls the comparison. A value equal to its parent or any relevant ancestor cannot appear in the tree.

Consider:

    5
   / \
  1   4
     / \
    3   6

Node 3 is smaller than its parent 4, so that local comparison looks correct. But 3 is inside the root's right subtree, where every value must be greater than 5. The node is illegal because the root still constrains it.

The direction is therefore:

Traverse downward, carrying the tightest legal interval for the current subtree.

Why checking only children fails

A local check might apply rules like these:

node.left.val < node.val < node.right.val

That can catch some invalid trees, but it cannot express all ancestor constraints. A node can be correctly ordered relative to its parent and still violate the value range imposed by an older ancestor.

For example:

      5
     / \
    4   6
       /
      3

Node 3 is less than 6, so it is a valid left child of 6. But it is also in the right subtree of 5, which means it must be greater than 5. The local check misses the violation.

A correct repeated-scan approach could inspect every node in a subtree and verify it against each ancestor's rule. That is logically sound, but it repeats work. The same descendants may be scanned again for multiple ancestors. On a skewed tree, this can grow to quadratic time.

The more useful decomposition is to turn each root-to-node path into two obligations:

1. The node must be greater than every ancestor where the path turned right.
2. The node must be smaller than every ancestor where the path turned left.

You do not need to store every ancestor. You only need:

• The largest lower restriction created by a right turn.
• The smallest upper restriction created by a left turn.

This is a common tree DFS recognition cue:

If a node's legality depends on decisions made along the path from the root, carry that path context downward.

Derive the bounds-based DFS

At the root, no ancestor has restricted the value yet. Its legal interval is unbounded:

(-infinity, +infinity)

For each node, perform four steps:

1. If the subtree is empty, it is valid.
2. Reject the node if its value is not strictly inside the current interval.
3. Validate the left subtree with a tighter upper bound.
4. Validate the right subtree with a tighter lower bound.

Suppose the current node has value x and arrives with the interval (lower, upper).

• Every value in the left subtree must be less than x, so its interval becomes (lower, x).
• Every value in the right subtree must be greater than x, so its interval becomes (x, upper).

The old bound remains in place. That is the important part. Moving left changes the upper bound but preserves the lower bound. Moving right changes the lower bound but preserves the upper bound.

Pseudocode

validate(node, lower, upper):
    if node is empty:
        return true

    if node.val <= lower or node.val >= upper:
        return false

    return validate(node.left, lower, node.val)
       and validate(node.right, node.val, upper)

The initial call uses unbounded endpoints.

The comparisons must be strict. Replacing < and > with <= or >= in the wrong direction is a common source of duplicate-handling bugs.

The recursive invariant

The helper should have a precise contract:

validate(node, lower, upper) is called only when every value in node's subtree must lie strictly inside (lower, upper). The interval summarizes all relevant constraints imposed by the ancestors.

That invariant explains both the code and the bound updates.

Base case

An empty subtree contains no value that can violate the interval. Therefore:

validate(None, lower, upper) == True

Current node

If node.val <= lower or node.val >= upper, the node violates an ancestor or parent constraint. The entire tree is invalid, so the helper returns False.

If the value is inside the interval, the current node satisfies every constraint represented by that interval.

Recursive step

For the left child, the current node becomes the new upper bound:

validate(node.left, lower, node.val)

Every left descendant must be less than node.val, while all earlier lower constraints still apply.

For the right child, the current node becomes the new lower bound:

validate(node.right, node.val, upper)

Every right descendant must be greater than node.val, while all earlier upper constraints still apply.

The two recursive calls preserve the invariant. If both return True, every value in both subtrees satisfies the complete set of ancestor restrictions.

Only the tightest bounds are needed because weaker bounds are redundant. If the current lower bound is already the largest value that a node must exceed, remembering smaller lower bounds adds no information. The same reasoning applies to the smallest upper bound.

Python implementation

Here is an interview-ready validate BST Python implementation using None for an unbounded endpoint:

def isValidBST(root):
    def is_valid(node, lower, upper):
        if node is None:
            return True

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

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

        return (
            is_valid(node.left, lower, node.val)
            and is_valid(node.right, node.val, upper)
        )

    return is_valid(root, None, None)

The state has a direct mapping to the problem:

• node is the subtree currently being validated.
• lower is the strict minimum value allowed by earlier right turns.
• upper is the strict maximum value allowed by earlier left turns.

The and expression also gives the desired short-circuit behavior. The current node is checked first. Then the left subtree is explored. If either check fails, Python does not need to validate the remaining subtree.

You can also use float("-inf") and float("inf") as initial bounds:

def isValidBST(root):
    def is_valid(node, lower, upper):
        if node is None:
            return True
        if not lower < node.val < upper:
            return False
        return (
            is_valid(node.left, lower, node.val)
            and is_valid(node.right, node.val, upper)
        )

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

For the stated integer range, Python can compare integer node values safely with those floating-point infinities. Still, None makes the unbounded condition explicit and avoids choosing any numeric sentinel that might accidentally collide with a valid input value.

Python integers also avoid fixed-width integer overflow when values are passed as bounds. In languages with fixed-width integers, use a wider type or explicit “bound exists” flags rather than assuming that minimum - 1 and maximum + 1 are always representable.

Dry-run the interval state

The range is easier to debug when you write down the interval entering each recursive call.

Consider the valid tree:

        5
       / \
      3   7
     / \ / \
    2  4 6  8

The important calls are:

Node	Incoming interval	Result
5	(-∞, +∞)	valid
3	(-∞, 5)	valid
2	(-∞, 3)	valid
4	(3, 5)	valid
7	(5, +∞)	valid
6	(5, 7)	valid
8	(7, +∞)	valid

Notice what happens at node 4. It is not merely “less than 5.” Because the path went left from 5 and right from 3, its actual interval is (3, 5).

Now trace the invalid tree:

      5
     / \
    1   4
       / \
      3   6

The calls include:

Node	Incoming interval	Result
5	(-∞, +∞)	valid
1	(-∞, 5)	valid
4	(5, +∞)	valid
3	(5, 4)	invalid

The interval at 3 is impossible: its lower bound is 5, while its upper bound is 4. The comparison fails immediately because 3 <= 5.

The debugging rule is simple:

• Move left: tighten the upper bound.
• Move right: tighten the lower bound.

If your code passes the parent-child examples but fails a deeper tree, print these incoming bounds. The missing ancestor constraint usually becomes visible at once.

Bounds recursion versus inorder validation

There is another valid approach: inorder traversal.

A binary search tree visited in left-node-right order produces values in strictly increasing order. Therefore, an inorder validator can keep the previously visited value and reject whenever the current value is less than or equal to it.

At a high level:

previous = no value yet

inorder(node):
    if node is empty:
        return true

    if inorder(node.left) is false:
        return false

    if previous exists and node.val <= previous:
        return false

    previous = node.val
    return inorder(node.right)

This is inorder BST validation: instead of carrying an interval down the tree, it checks whether the traversal produces a strictly increasing sequence.

The tradeoff is mostly about which invariant you want to make visible:

• Bounds recursion mirrors the BST definition directly. Every node is checked against the ancestor constraints that reach it.
• Inorder validation is compact once you are comfortable with traversal state. It validates the equivalent sorted-order property.

I recommend bounds recursion as the primary solution for this problem because it exposes the deeper pattern: subtree legality can be represented as a range passed through the traversal. The inorder version is worth knowing, but it should not replace understanding why ancestor constraints exist.

Edge cases and complexity

Empty tree

An empty subtree is valid. The helper returns True when node is None.

The problem's input constraints may require at least one node, but handling the empty case costs nothing and makes the recursive contract complete.

Single node

A single node lies inside the initial unbounded interval, so the result is True.

Duplicates

Duplicates fail because the bounds are strict:

node.val <= lower
node.val >= upper

This catches both direct duplicates and deeper duplicates. For example, a value equal to the root is invalid even if it appears several levels below the root.

Integer extremes

Valid values can include:

-2^31
2^31 - 1

Do not initialize bounds with arbitrary values such as -2^31 and 2^31 - 1 if those values themselves are allowed. A root equal to one of those sentinels could be rejected incorrectly.

Use None, infinities, or a wider numeric representation for unbounded endpoints.

Skewed trees

A tree with only left children or only right children still works. The interval simply tightens in one direction at each level.

The recursive implementation uses:

• Time: O(n), because each node is visited once and each visit performs constant-time comparisons.
• Auxiliary space: O(h), where h is the tree height, because the recursion stack stores one frame per active level.
• Worst-case recursive space: O(n) for a completely skewed tree.
• Balanced-tree recursive space: O(log n) when the height is logarithmic.

Do not claim constant auxiliary space for this recursive version. An iterative implementation can replace the call stack with an explicit stack, but it still stores path state and has O(h) auxiliary space.

In Python, a very deep skewed tree can also run into the runtime's recursion-depth limit. If the environment allows arbitrarily deep trees, use an explicit stack or account for that runtime constraint during the interview.

The transferable pattern

The useful lesson is larger than this one BST check.

When a tree node is constrained by decisions along the root-to-node path, checking only the parent is too little information. Carry the tightest valid context downward.

For this problem, that context is a strict lower and upper bound:

• Left turns tighten the ceiling.
• Right turns raise the floor.
• The current node must fit between them.

When you meet an unfamiliar tree problem, ask two questions before writing code:

1. What decisions made above this node still constrain it?
2. Can those constraints be compressed into a small state passed through DFS?

If the answer is yes, the recursive state is usually the algorithm. Range invariants turn a vague “the whole subtree must be ordered” requirement into two values you can inspect, test, and prove.