Validate a BST Explained: Tracing [5,4,6,null,null,3,7]

Imagine you are handed the binary tree representation [5, 4, 6, null, null, 3, 7]. Your goal is to determine whether it is a valid Binary Search Tree (BST) where every left descendant is strictly less than its ancestor and every right descendant is strictly greater. If you only check local relationships—asking whether each child is correctly positioned relative to its immediate parent—you will easily miss global violations hidden deeper in the branches.

Consider the root node 5. Its left child is 4 ($4<5$) and its right child is 6 ($6>5$). Moving down to the right child 6, its left child is 3 and its right child is 7. Locally, 3 is less than 6, and 7 is greater than 6. Everything looks correct at first glance. However, a deeper inspection reveals a critical flaw: 3 sits inside the right subtree of 5, yet $3<5$, violating the foundational rule of a BST.

Without a global mechanism to track allowed value boundaries across the entire path from the root, local checks give a false sense of security. We need a systematic way to propagate constraints down the tree so that distant ancestors can restrict the valid ranges of their descendants.

To see why a global rule is required for the tree [5, 4, 6, null, null, 3, 7], we must abandon the local view where a node only checks its immediate children. Instead, imagine each node in the tree as living inside a strictly enforced valid numerical window, defined by an open interval .

When we start at the root node 5, it has no ancestors, meaning its allowed value range is initially unbounded: $(-\infty ,\infty )$. As we branch down into the tree, we narrow this window based on the path we take:

- Moving to the left child (4) means all values in that entire left subtree must be strictly less than 5. Our upper bound updates to 5, yielding the window $(-\infty ,5)$.
- Moving to the right child (6) means all values in that entire right subtree must be strictly greater than 5. Our lower bound updates to 5, yielding the window $(5,\infty )$.

Now, trace what happens when we descend from root 6 to its left child, which holds the value 3. Because 3 is in the left child position of 6, our upper bound becomes 6, creating the active window $(5,6)$ for that node. But wait! The node's value is 3, and 3 does not fall inside $(5,6)$. This geometric violation instantly flags the tree as invalid without ever needing to look further down.

5 (-inf, inf)
/ \
4 6 (5, inf)
/ \
3 7
[fails (5, 6)]

Try this: Given root = 5, left = 4, right = 6. What is the active validation window for the right child 6's right child 7?

Now that we model BST validation as passing down a valid numeric interval $(low,high)$, let us run our recursive function on our locked example: the tree represented by [5, 4, 6, null, null, 3, 7]. We will trace every step, every interval update, and every return value.

Given

- Root node: 5
- Left child of 5: 4 (leaf node)
- Right child of 5: 6
- Left child of 6: 3
- Right child of 6: 7

1. Root Check: We start at the root node 5 with an initial valid window of $(-\infty ,\infty )$. Is 5 strictly between $-\infty$ and $\infty$? Yes. We branch to both children, narrowing our window:
- Left branch receives: $(-\infty ,5)$
- Right branch receives: $(5,\infty )$

2. Left Subtree (4): We evaluate node 4 with the window $(-\infty ,5)$. Is $4<5$? Yes. Node 4 has no children, so its recursive calls return true. The left branch of the tree is valid.

3. Right Subtree (6): We evaluate node 6 with the window $(5,\infty )$. Is $5<6<\infty$? Yes. Now, we narrow the window further for 6's children:
- Left child of 6 receives: $(5,6)$ because upper bound drops to node 6's value.
- Right child of 6 receives: $(6,\infty )$ because lower bound rises to node 6's value.

4. Deep Left Child (3): We evaluate node 3 with the window $(5,6)$. We check the condition $5<3<6$. This evaluates to false because 3 is not greater than 5.

Result

The recursive call for node 3 immediately returns false. This failure bubbles up through node 6 and back to the root, confirming the entire tree is invalid.

# Intermediate state during validation of node 3:
# validate(node=3, low=5, high=6)
# check: 5 < 3 -> False

def isValidBST(root, low=float('-inf'), high=float('inf')):
    if not root:
        return True
    if not (low < root.val < high):
        return False
    return (isValidBST(root.left, low, root.val) and 
            isValidBST(root.right, root.val, high))

Now that you have traced the recursive window validation on the original tree [5,4,6,null,null,3,7], it is time to test your mental model on a modified structure. Consider what happens when we fix that rogue right-subtree node. Suppose our tree is now [5, 4, 6, null, null, 5, 7] where node 3 has been replaced by 5 as the left child of 6.

Take out a notepad and trace the $(low,high)$ window for this modified tree. Start at the root 5 with bounds $(-\infty ,\infty )$. Go left to 4 with bounds $(-\infty ,5)$, and right to 6 with bounds $(5,\infty )$. When you evaluate the left child of 6, which now holds value 5, what does the validation check low < node.val < high evaluate to? Remember that a strict BST requires every node in the right subtree to be strictly greater than the root 5.

Work through the recursive calls for each node from top to bottom, recording the exact $(low,high)$ interval at every step before deciding whether the final result is true or false.

Try this: Tree: [5, 4, 6, null, null, 5, 7]
Question: Is this modified tree a valid BST? Trace the window for node 5 (left child of 6).

We have seen how our locked example [5, 4, 6, null, null, 3, 7] exposes a global violation hidden deep in the right subtree. Local parent-child checks (node.left.val < node.val < node.right.val) miss the fact that node 3 is in the right subtree of root 5 and violates the global $5<3$ invariant. By passing down an accumulating bounded window $(low,high)$, our recursive traversal correctly flagged 3 as out of bounds.

Now, let us transfer this exact interval-tracking mindset to a structural variant of our locked example. Imagine we mutate the tree layout while keeping the same core values: what if we place a rogue node in the left subtree that violates the upper bound? The transfer challenge is to adapt your mental model from checking lower bounds to simultaneously managing both upper and lower boundaries in unfamiliar tree geometries.

When encountering new binary tree validation problems—such as checking if a tree is a valid Max-Heap or verifying BST properties under duplicate rules—the key is to identify what parameter acts as the accumulating constraint. Just as the $(low,high)$ window contracts at every step for a BST, other tree properties rely on passing state down the call stack rather than inspecting single nodes in isolation.