Validate BST: Range Checking vs Inorder

You are given the root of a binary tree. Determine if it is a valid binary search tree (BST). A valid BST means that for every node, all values in its left subtree are strictly less than the node, and all values in its right subtree are strictly greater.

This is LeetCode 98: Validate Binary Search Tree, and it is one of the most commonly failed medium-difficulty tree problems. Not because the concept is hard, but because of one specific trap that catches people over and over.

The trap everyone falls into

The first thing most people try is checking whether each node's value is greater than its left child and less than its right child. That works for the immediate children, but it completely misses the grandparent constraint.

Look at node 6 in the invalid tree above. It is a right child of 3, and 6 > 3, so that relationship looks fine. But node 6 is also inside the left subtree of 5. Every node in 5's left subtree must be less than 5. Node 6 violates that rule.

This is the key insight: a node does not just need to satisfy its parent. It needs to satisfy every ancestor above it. As you go deeper into the tree, the valid range for each node gets tighter and tighter.

Approach 1: Range checking (recursive bounds)

The clean way to handle this is to pass an allowed range down to each node. The root can be anything from negative infinity to positive infinity. When you go left, the upper bound tightens to the current node's value. When you go right, the lower bound tightens to the current node's value.

def is_valid_bst(root):
    def check(node, low, high):
        if node is None:
            return True
        if node.val <= low or node.val >= high:
            return False
        return (check(node.left, low, node.val) and
                check(node.right, node.val, high))

    return check(root, float('-inf'), float('inf'))

Let's trace through the valid tree [5, 3, 8, 1, 4]:

• check(5, -inf, inf): 5 is in range. Go left with (-inf, 5), go right with (5, inf).
• check(3, -inf, 5): 3 is in range. Go left with (-inf, 3), go right with (3, 5).
• check(1, -inf, 3): 1 is in range. Both children are null. Returns True.
• check(4, 3, 5): 4 is in range. Both children are null. Returns True.
• check(8, 5, inf): 8 is in range. Both children are null. Returns True.
• Everything checks out. Return True.

Now trace through the invalid tree [5, 3, 8, 1, 6]:

• check(5, -inf, inf): 5 is in range. Go left with (-inf, 5).
• check(3, -inf, 5): 3 is in range. Go right with (3, 5).
• check(6, 3, 5): 6 >= 5. Out of range. Return False.

The range checking catches the violation immediately. Node 6 must be between 3 and 5, but it is not.

Approach 2: Inorder traversal

There is a completely different way to think about this problem. A binary search tree has a special property: if you do an inorder traversal (left, node, right), the values come out in sorted order. If the inorder sequence is not strictly increasing, the tree is not a valid BST.

The inorder traversal of our valid tree produces [1, 3, 4, 5, 8]. Each value is strictly greater than the previous one, so it is a valid BST.

Here is the code. You just need to track the previously visited value and make sure the current value is always larger:

def is_valid_bst(root):
    prev = [float('-inf')]

    def inorder(node):
        if node is None:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)

    return inorder(root)

Why use prev = [float('-inf')] instead of a plain variable? In Python, a nested function can read a variable from the enclosing scope, but it cannot reassign it without the nonlocal keyword. Using a list (and mutating prev[0]) sidesteps that. You could also use nonlocal prev if you prefer.

The logic: traverse left, then check whether the current node's value is greater than the last value we saw. If yes, update the last value and traverse right. If no, this is not a valid BST.

Which approach should you use?

Both are correct and have the same complexity. Here is when each one shines:

Range checking is better when:

• You want to explain the solution clearly in an interview. The bounds make the logic very explicit.
• The tree is likely invalid. Range checking can catch violations early without completing the entire traversal.
• You find it more intuitive to think about "what range is this node allowed in?"

Inorder traversal is better when:

• You already understand inorder traversal deeply and can write it without thinking.
• The problem is a variation that asks about sorted order (like finding two swapped nodes).
• You prefer the elegance of reducing the problem to "check if a sequence is sorted."

For interviews, the range checking approach is usually easier to explain and reason about. Learn both, but lead with range checking.

Complexity analysis

Time is O(n) for both. In the worst case (a valid tree), you visit every node exactly once.

Space is O(h) where h is the height of the tree. Both solutions use recursion, so the call stack grows as deep as the tree. For a balanced tree, h = log n. For a completely skewed tree, h = n.

An iterative inorder traversal using an explicit stack would use the same O(h) space but avoids the risk of stack overflow for extremely deep trees. For LeetCode constraints, the recursive versions are perfectly fine.

Edge cases to watch for

• Empty tree (root is None): return True. An empty tree is a valid BST. The base case handles this.
• Single node: return True. No children to violate any constraints.
• Duplicate values: a BST requires strictly less than and strictly greater than. If you see node.val == low or node.val == high, that is invalid. The <= and >= checks in the range approach handle this correctly.
• All nodes in a line (skewed tree): works fine, but the call stack goes O(n) deep. The traversal still visits every node in order.
• Large values (including negative numbers): using float('-inf') and float('inf') as initial bounds handles this. Some solutions use None for the initial bounds and skip the comparison if the bound is None, which also works.

The building blocks

This problem is built on one fundamental building block: inorder BST properties (inorder-bst-properties).

The core idea is that a valid BST produces a sorted sequence when traversed inorder. This property is what makes BSTs useful for search: you can always narrow down which subtree to look in because left is smaller and right is larger.

Both approaches in this post are really just different ways to verify that property:

• Range checking verifies it top-down by narrowing the valid range at each node. If a node falls outside its allowed range, the inorder sequence would not be sorted at that point.
• Inorder traversal verifies it directly by walking the tree in sorted order and checking that each value is strictly greater than the previous one.

# Range checking skeleton:
def check(node, low, high):
    if node is None:
        return True
    if node.val <= low or node.val >= high:
        return False
    return check(node.left, low, node.val) and check(node.right, node.val, high)

# Inorder skeleton:
def inorder(node):
    if node is None:
        return True
    if not inorder(node.left):
        return False
    # check current node against previous
    return inorder(node.right)

This building block shows up in problems like Kth Smallest Element in a BST, Convert BST to Greater Tree, and Recover BST (find two swapped nodes). Whenever you see "BST" in a problem title, your first thought should be: inorder traversal gives me sorted order.

From understanding to recall

You just worked through two complete solutions and traced them through valid and invalid trees. Right now, you can see exactly why range checking catches the grandparent violation and why inorder traversal reduces the problem to checking a sorted sequence. It all makes sense.

But here is the thing. In two weeks, when you see a BST problem in an interview, will you remember to pass bounds down the recursion? Will you remember that the upper bound tightens when you go left and the lower bound tightens when you go right? Or will you fall into the same trap as everyone else and only check immediate children?

Understanding and recall are different skills. Spaced repetition bridges the gap. You practice typing the range checking solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the base case, the range check, and the recursive calls with tightened bounds. After a few reps, the pattern is automatic.

The inorder BST properties building block appears in at least half a dozen LeetCode problems. Learning it once and drilling it with spaced repetition is far more effective than re-deriving it every time you hit a BST question.

Related posts

• Maximum Depth of Binary Tree - Uses the same recursive null base case pattern with a simpler combine step, a great warm-up before tackling BST validation
• Invert Binary Tree - Another tree recursion problem that modifies or inspects the tree structure using the same recursive skeleton