If you’ve ever felt completely lost looking at code that validates a Binary Search Tree (BST), you’re not alone. I’ve been there — staring at min and max parameters flying around in recursion, wondering what it all means.

Today, I want to share how I finally cracked the code behind validating a BST and why thinking of it as a game of setting boundaries made everything click.

The Problem: What Does It Mean to Validate a BST?

A BST follows one simple rule:

For every node, all nodes in its left subtree have smaller values, and all nodes in its right subtree have bigger values.

At first, I thought, “Cool, just check if the left child is smaller than the node and the right child is bigger.” But that’s not enough! What if a node deeper in the left subtree is bigger than the root? That breaks the BST property but simple checks don’t catch it.

The Key Insight: Each Node Has Boundaries

To truly validate a BST, each node needs to fit within a valid range of values.

The root node can be any value — so it has no boundaries.
When moving to the left child, the node must be smaller than its parent.
When moving to the right child, the node must be greater than its parent.

But it doesn’t stop there — as you go down the tree, the boundaries keep updating based on all ancestors, not just the immediate parent!

The Code That Finally Made Sense

Here’s the function I used:

def is_BST(node, min_val, max_val):
    if node is None:
        return True  # An empty tree is valid

    # Check if current node violates the boundaries
    if node.value <= min_val or node.value >= max_val:
        return False

    # Recursively check the left and right subtrees with updated boundaries
    left_is_valid = is_BST(node.left, min_val, node.value)
    right_is_valid = is_BST(node.right, node.value, max_val)

    return left_is_valid and right_is_valid

How It Works

For each node, check if its value is between min_val and max_val.
When moving to the left child, the max boundary becomes the current node’s value.
When moving to the right child, the min boundary becomes the current node’s value.
If any node breaks its boundary rules, return False.

Common Mistakes I Made

Only checking immediate children — I missed cases where deeper nodes violated BST rules.
Mixing up min and max arguments — caused wrong validations.
Forgetting to set initial boundaries to infinity — the first call must allow any value.

Seeing It Like a Game of Boundaries

I like to think of this validation like a game:

“Each node is given a range of allowed values. If the node’s value falls outside this range, it loses.”

When you go left, you shrink the maximum allowed value.
When you go right, you raise the minimum allowed value.

If every node passes this test, the tree is a valid BST!

Example Usage

root = Node(10)
root.left = Node(5)
root.right = Node(15)

print(is_BST(root, float('-inf'), float('inf')))  # True

root.left = Node(13)  # Invalid because 13 > 10 but on the left

print(is_BST(root, float('-inf'), float('inf')))  # False

Full Code Combined

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

def is_BST(node, min_val, max_val):
    if node is None:
        return True  # An empty tree is valid

    if node.value <= min_val or node.value >= max_val:
        return False

    left_is_valid = is_BST(node.left, min_val, node.value)
    right_is_valid = is_BST(node.right, node.value, max_val)

    return left_is_valid and right_is_valid

# Example 1: Valid BST
root = Node(10)
root.left = Node(5)
root.right = Node(15)
print(is_BST(root, float('-inf'), float('inf')))  # True

# Example 2: Invalid BST
root.left = Node(13)  # Left child is bigger than root, invalid BST
print(is_BST(root, float('-inf'), float('inf')))  # False

Final Thoughts

Validating a BST doesn’t have to be confusing once you see it as setting and checking boundaries on every node. This approach helped me move past the fog and understand what’s really going on under the hood.

If you’re learning trees or struggling with recursion, keep pushing — it will click!

How I Finally Understood Validating a Binary Search Tree (BST)