How to Validate a Binary Search Tree: The Range Method

"Is this binary tree a valid binary search tree?" Most first attempts compare every node with its two children, and most of them pass the example in the prompt. Then they fail on a tree where every parent-child pair looks correct and the tree is still wrong. The fix is one extra idea: a node answers to all of its ancestors, not just its parent.

The problem it solves

A binary search tree promises that for every node, every value in its left subtree is smaller and every value in its right subtree is larger. That promise is what makes search, insertion and ordered traversal work in O(h) steps, where h is the height. Code that trusts a broken tree gives wrong answers quietly: a search walks left and misses a value that was misplaced on the right.

Validation answers one question: does the promise hold at every node?

The intuition

Consider 5 with a left child 3, and give 3 a right child 6. Check pairs: 3 < 5, fine; 6 > 3, fine. Every local comparison passes. But 6 sits in the left subtree of 5, so it must be below 5, and it is not.

The rule that 6 broke came from its grandparent. So instead of comparing with the parent, carry the whole allowed range down the tree:

• The root may be anything: the range is (-inf, +inf).
• Stepping left from a node with value v keeps the floor and lowers the cap to v.
• Stepping right keeps the cap and raises the floor to v.

Each node is then checked against one open interval that already summarises every ancestor above it. In the example, 3 gets (-inf, 5) and 6 gets (3, 5), and 6 fails.

There is a second way to see the same property. An in-order traversal — left subtree, node, right subtree — visits a valid BST's values in sorted order. So a tree is a valid BST exactly when its in-order sequence strictly increases. That gives an iterative check with a single prev variable.

Watch it run

The animation draws the four-node tree from above. The root gets (-inf, +inf), the step left caps the range at 5, and the step right from 3 raises the floor to 3. The node 6 beats its parent and still falls outside (3, 5). Change it to 4 and the same walk passes; the right side checks 8 against (5, +inf).

The code

Three checks: the tempting parent-only version, the range version, and the in-order version.

import math

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def parent_only(node):                 # the tempting check, and it is wrong
    if node is None:
        return True
    if node.left and not node.left.val < node.val:
        return False
    if node.right and not node.val < node.right.val:
        return False
    return parent_only(node.left) and parent_only(node.right)

def is_bst(node, low=-math.inf, high=math.inf):
    if node is None:
        return True
    if not low < node.val < high:       # the inherited range, not the parent
        return False
    return (is_bst(node.left, low, node.val) and     # left: cap drops to val
            is_bst(node.right, node.val, high))      # right: floor rises to val

def is_bst_inorder(root):              # same answer, no recursion
    stack, prev, node = [], -math.inf, root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if node.val <= prev:            # in-order must strictly increase
            return False
        prev, node = node.val, node.right
    return True

bad = Node(5, Node(3, None, Node(6)), Node(8))    # 6 is right of 3, left of 5
print(parent_only(bad), is_bst(bad), is_bst_inorder(bad))        # True False False
fixed = Node(5, Node(3, None, Node(4)), Node(8))
print(parent_only(fixed), is_bst(fixed), is_bst_inorder(fixed))  # True True True

To test them, a brute-force checker applies the definition literally: collect every value in each subtree and compare it with the node. It runs on 4,000 trees — half random shapes with small repeated values, half real BSTs built by insertion so that valid trees are well represented. A 5,000-node chain is added at the end to show a practical difference between the two correct versions:

import random

def values(node):
    return [] if node is None else values(node.left) + [node.val] + values(node.right)

def brute(node):                       # the definition, checked literally
    if node is None:
        return True
    return (all(v < node.val for v in values(node.left)) and
            all(v > node.val for v in values(node.right)) and
            brute(node.left) and brute(node.right))

def random_tree(n):
    if n == 0:
        return None
    k = random.randint(0, n - 1)
    return Node(random.randint(0, 9), random_tree(k), random_tree(n - 1 - k))

def insert(node, v):
    if node is None:
        return Node(v)
    if v < node.val:
        node.left = insert(node.left, v)
    elif v > node.val:
        node.right = insert(node.right, v)
    return node

random.seed(8)
ok, valid, parent_wrong = True, 0, 0
for i in range(4000):
    if i % 2:
        tree = random_tree(random.randint(0, 8))
    else:
        tree = None
        for v in random.sample(range(30), random.randint(0, 12)):
            tree = insert(tree, v)
    truth = brute(tree)
    ok &= is_bst(tree) == truth == is_bst_inorder(tree)
    valid += truth
    parent_wrong += parent_only(tree) != truth
print(ok, valid, parent_wrong)          # True 2565 29

chain = None
for v in range(5000, 0, -1):            # 1 -> 2 -> ... -> 5000, all right children
    chain = Node(v, None, chain)
print(is_bst_inorder(chain))            # True
try:
    is_bst(chain)
except RecursionError:
    print("RecursionError")             # RecursionError

The range and in-order checks agree with the brute force on every tree. The parent-only check got 29 of them wrong, each one a tree where some node obeys its parent but breaks the bound of an ancestor further up.

The complexity

Both correct versions visit each node once and do constant work there: O(n) time. The extra memory is the depth of the walk, O(h): the call stack for the recursive version, the explicit stack for the in-order one. On a balanced tree h is about log n; on a chain it is n, which is exactly what the last lines show. Python's default recursion limit is 1,000 frames, so the recursive check fails on the chain while the explicit stack does not mind.

Where it goes wrong

• Comparing with the parent only. Shown above: every local pair can be fine while the tree is not.
• Sentinels that are real values. Using 0 or the smallest 32-bit integer as the starting floor rejects a tree that legitimately contains that value. Use infinities, or None for "no bound".
• Duplicates. The strict test low < val < high rejects equal values. If the tree you are given allows duplicates on one side, say so and make that side non-strict — it is a choice, not a detail.
• Recursion depth. A skewed tree turns an elegant recursion into a crash. Mention the iterative version when the input size is unknown.

How to say it in an interview

"Each node has to respect every ancestor, not only its parent, so I pass down an open interval. Going left, the node's value becomes the new upper bound; going right, it becomes the new lower bound. Each node is checked once, so it's O(n) time and O(h) space. Equivalently, an in-order traversal of a valid BST is strictly increasing, and I can check that iteratively if the tree might be deep."

If you want the reason BSTs are worth validating at all, BST insert and search walks the path that depends on the ordering rule.