Validate Binary Search Tree

You'll pass each node a range of allowed values, so one DFS checks every ancestor's rule at once. You need binary trees. Related chapter: trees.

1. The problem

You get the root of a binary tree. Return whether it's a binary search tree (BST): at every node, the entire left subtree holds smaller values and the entire right subtree holds larger values. Equal values aren't allowed. Don't change the tree. Our function also treats an empty tree as valid. The inputs below list the tree level by level. This is LeetCode 98.

"Entire" is the word that matters. In the second example, 4 is fine as 8's left child, but it sits in 5's right subtree and is smaller than 5.

2. A correct baseline

For each node, collect every value below it and check them directly.

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

def values(root):
    result, pending = [], [root]
    while pending:
        node = pending.pop()
        if node is not None:
            result.append(node.val)
            pending.extend((node.left, node.right))
    return result

def baseline(root):
    if root is None:
        return True
    return (all(x < root.val for x in values(root.left))
            and all(x > root.val for x in values(root.right))
            and baseline(root.left) and baseline(root.right))

assert baseline(TreeNode(4, TreeNode(2), TreeNode(6)))
assert not baseline(TreeNode(5, TreeNode(3), TreeNode(8, TreeNode(4), TreeNode(9))))
assert not baseline(TreeNode(2, TreeNode(2), TreeNode(3)))
assert baseline(None)

On a chain of n nodes, each node collects everything below it, so this takes O(n²) time. On a 10,000-node chain, that's about 50 million values collected. It uses O(n) extra space.

The bottleneck. It checks each node against every ancestor separately, collecting the same values again and again.

3. The observation

Follow the second example down. At the root 5, any value is allowed. Going right, values must be above 5. Going left from 8, values must be below 8. So 4 must fall strictly between 5 and 8, and it doesn't.

Every ancestor adds a limit, but only the tightest two matter: the largest lower limit and the smallest upper limit. Going left, the current value becomes the new upper limit. Going right, it becomes the new lower limit. Check lower < value < upper, with strict <, which also rejects duplicates. Use None for "no limit". A made-up limit like -10**9 could wrongly reject a real value.

4. The solution and a trace

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

class Solution:
    def isValidBST(self, root) -> bool:
        """Acyclic binary tree with integer keys; strict order, empty is valid."""
        pending = [(root, None, None)]
        while pending:
            node, lower, upper = pending.pop()
            if node is None:
                continue
            # Bounds summarize all ancestor restrictions on this subtree.
            if lower is not None and node.val <= lower:
                return False
            if upper is not None and node.val >= upper:
                return False
            pending.append((node.right, node.val, upper))
            pending.append((node.left, lower, node.val))
        return True

solve = Solution().isValidBST
assert solve(TreeNode(4, TreeNode(2), TreeNode(6)))
assert not solve(TreeNode(5, TreeNode(3), TreeNode(8, TreeNode(4), TreeNode(9))))
assert not solve(TreeNode(2, TreeNode(2), TreeNode(3)))
assert solve(None)

Trace the second example, skipping empty children:

5. Why it works

What stays true. Every node on the stack carries exactly the range its ancestors allow.

Why that stays true. A node that passes lies inside its own range. So the narrower ranges it hands its children still respect every ancestor above it.

A False answer is right. A rejected value breaks some ancestor's rule.

A True answer is right. If every node passes, every value respects every ancestor's left/right rule, so the tree is a BST. The strict < takes care of duplicates.

6. Cost, edge cases, and failure

Cost. Each node is pushed and checked once: O(n) time. The stack holds O(h) entries for a tree of height h, which is O(n) for a chain. There's no recursion, and the tree isn't changed.

Edge cases. Negative values work. So do the smallest and largest 32-bit integers, because a missing limit is None, not a number.

Where it fails. Checking only each node's own children misses the problem:

root = TreeNode(5, TreeNode(3), TreeNode(8, TreeNode(4), TreeNode(9)))
def local_only(node):
    # Deliberately wrong: forgets ancestors above the parent.
    if node is None:
        return True
    return ((node.left is None or node.left.val < node.val)
            and (node.right is None or node.right.val > node.val)
            and local_only(node.left) and local_only(node.right))
assert local_only(root)
assert not solve(root)
assert solve(TreeNode(-(2**31), None, TreeNode(2**31 - 1)))

import random
rng = random.Random(98)
def random_tree(depth):
    if depth == 0 or rng.randrange(4) == 0:
        return None
    return TreeNode(rng.randrange(-5, 6), random_tree(depth - 1), random_tree(depth - 1))
def snapshot(root):
    nodes, pending = [], [root]
    while pending:
        node = pending.pop()
        if node is not None:
            nodes.append((node, node.val, node.left, node.right))
            pending.extend((node.left, node.right))
    return nodes
for _ in range(500):
    root = random_tree(6)
    before = snapshot(root)
    assert solve(root) == baseline(root)
    assert all(node.val == val and node.left is left and node.right is right
               for node, val, left, right in before)
    # Assign increasing inorder values to also test genuinely valid shapes.
    def assign(node, counter):
        if node is not None:
            assign(node.left, counter)
            node.val = next(counter)
            assign(node.right, counter)
    assign(root, iter(range(1000)))
    assert solve(root) and baseline(root)
chain = None
for value in range(9999, -1, -1):
    chain = TreeNode(value, None, chain)
assert solve(chain)