Validating a Binary Search Tree

The Obvious—But Flawed—Approach

Let's start by considering the definition of a BST. For any node, its left child must be smaller and its right child must be larger. A first attempt might be to write a function that recursively checks this for every node:

# THIS IS AN INCORRECT SOLUTION
def is_valid_bst_naive(node):
    if not node:
        return True
    
    # Check if the left child is smaller (if it exists)
    if node.left and node.left.val >= node.val:
        return False
        
    # Check if the right child is larger (if it exists)
    if node.right and node.right.val <= node.val:
        return False
        
    # Recursively check the subtrees
    return is_valid_bst_naive(node.left) and is_valid_bst_naive(node.right)

This approach seems logical, but it's wrong. Why? Because it only checks the relationship between a node and its immediate children. It fails to enforce the global BST property.

To see why, let's watch a short video that highlights this exact pitfall with a clear example.

The video uses an example like this:

      5
     / \
    1   7
       / \
      4   8

In this tree, 4 is correctly the left child of 7 (since 4 < 7), but it violates the overall BST property because 4 is in the right subtree of the root 5, and it is not greater than 5. The naive check would miss this.

This image provides another excellent visual comparison of a valid and an invalid BST, highlighting a similar violation.

The key takeaway is that every node must be within a range defined by all of its ancestors, not just its parent.

Approach 1: Recursive Validation with Boundaries

The most robust and intuitive solution is to perform a recursive traversal while keeping track of the valid range of values for each node.

The logic is as follows:

1. Start at the root. The valid range for the root is (-infinity, +infinity).
2. For any given node, check if its value falls within its valid range. If not, the tree is invalid.
3. When you recurse to the left child, the valid range narrows. The new upper bound becomes the parent's value. The lower bound stays the same. The range becomes (low, parent.val).
4. When you recurse to the right child, the valid range also narrows. The new lower bound becomes the parent's value. The upper bound stays the same. The range becomes (parent.val, high).

This video segment explains the boundary-passing technique very clearly.

Let's solidify this concept by looking at a well-structured article that presents the full Python implementation.

Here is the code from the article, which elegantly implements this logic using a helper function:

from typing import Optional

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

def isValidBST(root: Optional[TreeNode]) -> bool:
    
    def validate(node: Optional[TreeNode], low: float, high: float) -> bool:
        # An empty tree is a valid BST
        if not node:
            return True
            
        # The current node's value must be between low and high (exclusive)
        if not (low < node.val < high):
            return False
            
        # Recursively validate the left and right subtrees with updated bounds
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))

    # Initial call for the root with the widest possible range
    return validate(root, float('-inf'), float('inf'))

• Time Complexity: $O(N)$, where $N$ is the number of nodes, because we visit each node exactly once.
• Space Complexity: $O(H)$, where $H$ is the height of the tree. This space is used by the recursion call stack. In the worst case of a skewed tree, this can be $O(N)$. In a balanced tree, it's $O(\log N)$.

      5
     / \
    1   7
       / \
      4   8

Approach 2: In-Order Traversal

There is another elegant approach that relies on a key property of BSTs: an in-order traversal of a valid BST visits the nodes in ascending sorted order.

Recall that an in-order traversal follows the Left -> Root -> Right pattern. Because all nodes in the left subtree are smaller than the root, and all nodes in the right subtree are larger, this traversal naturally produces a sorted sequence.

To validate a BST using this property, we can perform an in-order traversal and simply check if each node's value is strictly greater than the value of the previously visited node.

This video provides an excellent explanation of this concept.

While one way to implement this is to store the full in-order traversal in an array and check if it's sorted, that would require $O(N)$ space. A more optimized approach for an interview is to perform an iterative in-order traversal and check the sorted property on the fly, which only requires $O(H)$ space for the stack.

The article we looked at earlier also covers this optimized iterative implementation.

Here is the iterative in-order code. It's a standard pattern for iterative traversal that you should be familiar with for interviews.

def isValidBST_inorder(root: Optional[TreeNode]) -> bool:
    stack = []
    current = root
    prev_value = float('-inf')

    while stack or current:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left
        
        # Visit the node (pop from stack)
        current = stack.pop()
        
        # Check against the previous value
        if current.val <= prev_value:
            return False
        prev_value = current.val
        
        # Move to the right subtree
        current = current.right
        
    return True

This approach has the same time and space complexity as the recursive solution—$O(N)$ time and $O(H)$ space—but avoids the risk of a recursion depth error on very deep trees.

Conclusion

You've now learned two robust and efficient methods for validating a Binary Search Tree, a problem that effectively probes your fundamental understanding of this data structure.

Key Takeaways:

• The Pitfall: BST validation is a global property, not a local one. Simply checking a node against its immediate children is insufficient.
• Recursive Boundaries: The standard approach is a recursive traversal that passes down a (low, high) range, ensuring each node respects the constraints imposed by all its ancestors.
• In-Order Property: A powerful alternative is to leverage the fact that an in-order traversal of a valid BST yields a sorted sequence. You can check this property on the fly during an iterative traversal.
• Complexity: Both primary approaches achieve optimal performance with $O(N)$ time complexity and $O(H)$ space complexity.

In your next lesson, we will continue to build on these concepts by solving another common BST problem: finding the k-th smallest element in a BST. You'll see that the in-order traversal idea we discussed today is the key to solving that problem efficiently.