Validating Binary Search Trees via Bound Propagation

Hello again! In our last lesson, we explored a recursive pattern where we compute a tree's property by "bubbling up" results from the child subtrees. We used this post-order traversal style to calculate a tree's maximum and minimum depth.

Today, we'll tackle a different kind of recursive problem and learn a new, complementary pattern. Instead of passing information up the tree, we will pass constraints down from parent to child. This is a powerful technique for enforcing properties that must hold true for an entire subtree. Our goal is to apply this pattern to solve a classic interview problem: validating a Binary Search Tree (BST). Mastering this will add a crucial pre-order style recursive tool to your algorithmic thinking.

The Deceptive Simplicity of the BST Property

First, let's be precise about what a Binary Search Tree is. For any given node in the tree:

1. All values in its entire left subtree must be strictly less than the node's value.
2. All values in its entire right subtree must be strictly greater than the node's value.
3. Both the left and right subtrees must also be binary search trees.

The key words here are "entire subtree." This is a global property, not a local one. A very common mistake, especially when under pressure, is to assume that you only need to check a node's immediate children.

Let's see why that's wrong. The following resource from OneNoughtOne provides an excellent explanation of this common pitfall.

The NeetCode video below visualizes this exact same pitfall. Watching the explanation will help solidify why a simple parent-child check is insufficient.

The node 4 in the example is the problem. It's correctly placed as the left child of 7 (4 < 7), but it violates the global property established by the root 5, because 4 is in the right subtree of 5 but is not greater than 5.

The Correct Approach: Propagating Value Bounds

To solve this, we need a way to enforce the constraints from all ancestors as we traverse down the tree. The elegant solution is to pass down a permissible (lowerBound, upperBound) for each node.

The logic works like this:

1. The root node can be any value, so its initial range is (-Infinity, +Infinity).
2. When we traverse to a left child, we know its value must be less than its parent. So, we pass down the same lowerBound but update the upperBound to be the parent's value.
3. When we traverse to a right child, its value must be greater than its parent. So, we update the lowerBound to the parent's value and pass down the same upperBound.
4. At each node, we check if its value is strictly within its inherited (lowerBound, upperBound). If not, the tree is invalid. If the whole tree is traversed without any violations, it is a valid BST.

This image provides a perfect visualization of this "Min-Max Range Approach".

The video from NeetCode that you started earlier explains this exact process.

This method is a form of pre-order traversal. The "work"—checking the current node against its bounds—is done before the recursive calls to the children.

Implementation and Recursive Patterns

Let's look at how this translates into a recursive TypeScript function. We'll define a helper function that takes the current node and its valid (left, right) bounds as arguments.

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

function isValidBST(root: TreeNode | null): boolean {
    // We define a helper function to carry the bounds during recursion.
    function validate(node: TreeNode | null, lowerBound: number, upperBound: number): boolean {
        // 1. Base Case: An empty subtree is valid.
        if (node === null) {
            return true;
        }

        // 2. Pre-order work: Check if the current node is within its bounds.
        // Note the strict inequality.
        if (node.val <= lowerBound || node.val >= upperBound) {
            return false;
        }

        // 3. Recursive Step: Pass updated bounds to the children.
        // For the left child, the upper bound becomes the current node's value.
        // For the right child, the lower bound becomes the current node's value.
        return validate(node.left, lowerBound, node.val) && 
               validate(node.right, node.val, upperBound);
    }

    // Start the validation from the root with an infinite range.
    return validate(root, -Infinity, Infinity);
}

This implementation directly follows the logic we've discussed. It has a time complexity of $O(N)$ because we visit each node once. The space complexity is $O(H)$ (where $H$ is the tree height) due to the recursion call stack.

Notice the contrast with the maxDepth function from our previous lesson:

• maxDepth (Post-order): Information flows up. A node can only calculate its depth after its children have returned their depths. The work happens after the recursive calls. return 1 + Math.max(leftDepth, rightDepth);
• isValidBST (Pre-order): Information flows down. A node's validity is checked using bounds passed down from its parent. The work happens before the recursive calls. if (node.val <= lower || ...)

Recognizing these fundamental "pass-up" vs. "pass-down" patterns is a huge step toward demystifying tree algorithms.

Another Way: Inorder Traversal

It's always valuable to know there can be multiple ways to solve a problem. An alternative approach for BST validation relies on a special property: an inorder traversal of a valid BST will visit the nodes in strictly increasing order.

Why? Because inorder traversal visits left -> node -> right. By definition of a BST, everything on the left is smaller, and everything on the right is larger.

Therefore, you can perform an inorder traversal while keeping track of the previously visited node's value. If you ever encounter a node whose value is less than or equal to the previous one, you've found a violation.

The following text provides a quick summary of this approach. While our main focus is the bound-propagation method, it's good to be aware of this clever alternative.

The range-based method is often more direct as it encodes the BST definition itself. It can also terminate faster—as soon as it finds an invalid node, it can stop, whereas the inorder method may need to traverse deeper to find a value that breaks the sorted sequence.

Conclusion

In this lesson, we dissected the Binary Search Tree validation problem and uncovered a powerful recursive pattern.

Key Takeaways:

• BST Property is Global: A node's value must be valid with respect to all its ancestors, not just its immediate parent. Simple local checks are insufficient and a common trap.
• Propagate Bounds Downward: The correct recursive solution involves passing a (min, max) valid range down the tree. This is a "pre-order" style of recursion where work is done before recurring.
• Update Bounds Logically: When going left, the parent's value becomes the new upper bound. When going right, it becomes the new lower bound.
• Recognize Recursive Patterns: You now have two primary recursive tree patterns in your toolkit: "bubbling up" results (post-order, for problems like maxDepth) and "passing down" constraints (pre-order, for problems like isValidBST).

In our next lesson, we will tackle another common tree problem: finding the lowest common ancestor of two nodes. This will require us to synthesize our understanding of tree traversals and recursive state to locate specific nodes and track their paths from the root.