Skip to main content

Validate Binary Search Tree: The Designer's Discovery Journey

Abstractum​

Core Kernel Logic

The Fundamental Principle: Constraint Inheritance

BST validation is fundamentally about propagating ancestral constraints down the tree, not just checking local parent-child relationships.

The Kernel:

  • Each node must satisfy constraints inherited from ALL ancestors, not just its immediate parent
  • Going LEFT establishes an UPPER BOUND for all descendants
  • Going RIGHT establishes a LOWER BOUND for all descendants
  • Constraints accumulate and tighten as depth increases

The Implementation:

validate(node, min_val, max_val)
├─ Check: min_val < node.val < max_val
├─ Recurse left:  validate(node.left,  min_val,   node.val)  # inherit min, tighten max
└─ Recurse right: validate(node.right, node.val, max_val)    # tighten min, inherit max

Why This Works:

  • Node 12 in the right subtree of 10 must satisfy: > 10 (from ancestor) AND < 15 (from parent)
  • Local checks (12 < 15) miss the ancestral constraint (12 > 10)
  • Range [min, max] captures ALL inherited constraints in a single compact representation

The Pattern: Threaded state through recursion enables global validation using only local checks.

The Problem​

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as:

  • The left subtree of a node contains only nodes with keys less than the node's key
  • The right subtree of a node contains only nodes with keys greater than the node's key
  • Both left and right subtrees must also be binary search trees
def isValidBST(root):
    def validate(node, min_val, max_val):
        # Base case: empty tree is valid
        if not node:
            return True

        # Check if current node violates constraints
        if not (min_val < node.val < max_val):
            return False

        # Recursively validate subtrees with updated bounds
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    # Start with no constraints (-infinity, +infinity)
    return validate(root, float('-inf'), float('inf'))

The Designer's Journey: From Wrong to Right​

First Instinct (The Trap)​

Thought #1: "BST means left < parent < right. So I'll just check each node against its immediate children!"

# WRONG APPROACH
def isValidBST(root):
    if not root:
        return True

    # Check immediate children only
    if root.left and root.left.val >= root.val:
        return False
    if root.right and root.right.val <= root.val:
        return False

    # Recurse
    return isValidBST(root.left) and isValidBST(root.right)

Test Case That Breaks This:

Example 2: [5,1,4,null,null,3,6]
        5
       / \
      1   4
         / \
        3   6

Check at node 5: left(1) < 5 < right(4) ✓
Check at node 4: left(3) < 4 < right(6) ✓
Returns: TRUE (WRONG!)

Why invalid? Because 3 is in the right subtree of 5, but 3 < 5
Aha Moment #1

It's not just about immediate parent-child relationships. It's about ANCESTRY constraints.

Second Thought (Getting Warmer)​

Thought #2: "Every node in the left subtree must be less than the root. Every node in the right subtree must be greater than the root."

But wait... what about deeper levels?

        10
       /  \
      5    15
     / \   / \
    2   7 12  20
            \
             13

Analysis:

  • Node 13: Must be > 12 (its parent) ✓
  • Node 13: Must be > 15 (its grandparent) ✓
  • Node 13: Should it be < 10? NO! It should be > 10 because it's in the right subtree of 10.
Aha Moment #2

Each node doesn't just have a relationship with its children. Each node carries inherited constraints from all its ancestors.

The Key Insight (Prerequisites)​

The property that makes this solvable:

  1. When you go LEFT from a node, you're establishing an UPPER BOUND for all descendants
  2. When you go RIGHT from a node, you're establishing a LOWER BOUND for all descendants
        10
       /
      5    ← Everything here must be < 10 (upper bound)
     /
    2    ← Must be < 10 AND < 5 (tighter upper bound)
Critical Question

Can you see why this means we need to track a RANGE [min, max] as we traverse, not just single values?

Answer: Because constraints accumulate! Each step down the tree potentially makes the valid range smaller.

The Coder's Brain​

Data Structure Choice​

What do we need to track?

  1. Current node (obvious)
  2. The valid range this node must fall within (min, max)

Why min AND max?

  • When we go left: max becomes stricter (parent's value)
  • When we go right: min becomes stricter (parent's value)

Discovery process:

  1. "Should I store ranges in each node?" → ❌ No, BST nodes don't have that info
  2. "Should I pass ranges down as I recurse?" → ✅ Yes! This is state we compute during traversal

The Chronological Build​

Step 1: Base Case​

if not node:
    return True  # Empty tree is valid

Why this first? Because recursion needs a stopping condition. What's the simplest valid BST? Nothing!

Step 2: Check Current Node​

if not (min_val < node.val < max_val):
    return False

Why this second? Before recursing deeper, validate the current node against inherited constraints.

Edge case validator: What if min_val or max_val is None (no constraint yet)? We need to handle infinity!

Step 3: Recurse with Updated Bounds​

left_valid = validate(node.left, min_val, node.val)   # left must be < node.val
right_valid = validate(node.right, node.val, max_val) # right must be > node.val

Thought process:

  • Left child: Keep the same lower bound, but now upper bound = current node
  • Right child: Keep the same upper bound, but now lower bound = current node

Complete Solution​

def isValidBST(root):
    def validate(node, min_val, max_val):
        # Base case: empty tree is valid
        if not node:
            return True

        # Check if current node violates constraints
        if not (min_val < node.val < max_val):
            return False

        # Recursively validate subtrees with updated bounds
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))

    # Start with no constraints (-infinity, +infinity)
    return validate(root, float('-inf'), float('inf'))

Edge Cases as Concept Validators​

Test Case 1: Single Node Tree [5]​

validate(node=5, min=-∞, max=+∞)
# Is -∞ < 5 < +∞? Yes → Valid

Why does this work? Single nodes have no ancestors, so no constraints!

Test Case 2: Duplicate Values [2, 2, 2]​

    2
   /
  2
validate(node=2, min=-∞, max=+∞)  # Root is valid
validate(left=2, min=-∞, max=2)   # Is -∞ < 2 < 2? NO!
# Returns False

Why strict inequality? BST definition says "less than" not "less than or equal to"

Test Case 3: All Left Children [5, 3, 1]​

    5
   /
  3
 /
1
validate(5, -∞, +∞)     # Valid, recurse left
validate(3, -∞, 5)      # Valid, recurse left
validate(1, -∞, 3)      # Valid

Why do both inherit the 5 constraint? Because 3 passed down its own constraint (3), which is tighter than the inherited constraint from 5.

Tracing a Complex Example​

        10
       /  \
      5    15
     / \   / \
    2   7 12  20

Execution trace:

validate(10, -∞, +∞)           # Root: -∞ < 10 < +∞ ✓
├─ validate(5, -∞, 10)         # Left of 10: -∞ < 5 < 10 ✓
│  ├─ validate(2, -∞, 5)       # Left of 5: -∞ < 2 < 5 ✓
│  └─ validate(7, 5, 10)       # Right of 5: 5 < 7 < 10 ✓
└─ validate(15, 10, +∞)        # Right of 10: 10 < 15 < +∞ ✓
   ├─ validate(12, 10, 15)     # Left of 15: 10 < 12 < 15 ✓
   └─ validate(20, 15, +∞)     # Right of 15: 15 < 20 < +∞ ✓

Result: All checks pass → TRUE

Key observation: Notice how constraints get tighter as we go deeper. Node 12 has the range [10, 15], even though its parent is 15!

The "Recursive in If Condition" Pattern​

This problem uses a common pattern: using recursive calls directly in boolean expressions.

# Both must be true
return (validate(node.left, min_val, node.val) and
        validate(node.right, node.val, max_val))

What's happening:

  1. Evaluate left subtree → returns True/False
  2. If left returns False, short-circuit and return False immediately
  3. If left returns True, evaluate right subtree → returns True/False
  4. Return the combined result

Why not use intermediate variables?

# More verbose version
left_valid = validate(node.left, min_val, node.val)
if not left_valid:
    return False

right_valid = validate(node.right, node.val, max_val)
if not right_valid:
    return False

return True

Both work! The concise version uses Python's short-circuit evaluation.

The Meta-Process Framework​

When you see "validate tree property X":

  1. Test naive approach (immediate relationships only)
  2. Find counterexample that breaks naive approach
  3. Identify what information is being ignored (ancestry, global position)
  4. Ask: What constraints propagate down the tree?
  5. Design recursion that carries constraint state
The Universal Pattern

Tree problems often require passing accumulated context down during recursion, not just checking local properties.

Similar Problems Using This Pattern​

Problem: Validate Binary Tree Path Sum​

"Does there exist a root-to-leaf path with a given sum?"

def hasPathSum(root, target):
    def dfs(node, remaining):
        if not node:
            return False

        # Leaf node check
        if not node.left and not node.right:
            return remaining == node.val

        # Recursive calls with updated remaining sum
        return (dfs(node.left, remaining - node.val) or
                dfs(node.right, remaining - node.val))

    return dfs(root, target)

Pattern similarity: Passing down accumulated state (remaining sum)

Problem: Maximum Path Sum in Binary Tree​

"Find the maximum sum of any path in a binary tree"

def maxPathSum(root):
    max_sum = float('-inf')

    def dfs(node):
        nonlocal max_sum
        if not node:
            return 0

        # Only consider positive contributions
        left = max(0, dfs(node.left))
        right = max(0, dfs(node.right))

        # Update global max considering path through current node
        max_sum = max(max_sum, node.val + left + right)

        # Return max path going through this node upward
        return node.val + max(left, right)

    dfs(root)
    return max_sum

Pattern similarity: Maintaining global state while recursing with local decisions

Key Takeaways​

Remember
  1. Local checks aren't enough - Tree properties often require global validation
  2. Pass constraints down - Accumulated state captures ancestral relationships
  3. Trust your recursion - Focus on what the current node needs, delegate the rest
  4. Base cases matter - Empty trees and leaf nodes need special handling
  5. Strict inequalities - BST uses < and >, not ≤ and ≥
  6. Range thinking - Min/max bounds capture all inherited constraints
  7. Short-circuit evaluation - Use and/or for clean boolean recursion

The Discovery Process Summary​

The journey from confusion to clarity:

  1. ❌ Try immediate parent-child checks → Fails on deep violations
  2. ❌ Try checking "all left < root < all right" → Doesn't capture how to validate deeper
  3. 💡 Realize constraints propagate from ancestors
  4. 💡 Recognize need for range tracking [min, max]
  5. ✅ Design recursion passing ranges down
  6. ✅ Update ranges at each step based on direction
  7. ✅ Validate against ranges, not just parent

The meta-lesson: When local validation fails, think about what global context you're missing and how to thread it through your recursion.

Summary: The Core Logic Distilled​

Essential Understanding

The Problem: How do we validate that EVERY node in a tree satisfies BST properties relative to ALL its ancestors?

Why Naive Approaches Fail:

  • ❌ Checking only parent-child relationships misses ancestral violations
  • ❌ Node 3 can be < 4 (its parent) but violate 3 < 5 (its grandparent)

The Core Insight: Constraint Inheritance

Every node exists within a valid range [min, max] determined by its ancestry:

        10                      Range: (-∞, +∞)
       /  \
      5    15                   Left of 10:  (-∞, 10)
     / \   / \                  Right of 10: (10, +∞)
    2   7 12  20                Left of 15:  (10, 15) ← Notice: inherits 10!

The Three-Step Algorithm:

  1. Receive inherited constraints: validate(node, min, max)
  2. Check current node: Is min < node.val < max?
  3. Pass updated constraints:
    • Left child: validate(node.left, min, node.val) ← tighten upper bound
    • Right child: validate(node.right, node.val, max) ← tighten lower bound

Why This Works:

  • Each node only needs to check against its immediate range
  • The range encapsulates ALL ancestral constraints
  • Constraints propagate and accumulate automatically through recursion
  • No need to track or query ancestors explicitly

The Meta-Pattern: When tree properties depend on relationships beyond immediate parent-child:

  1. Identify what constraints propagate from ancestors
  2. Design a compact representation (here: [min, max] range)
  3. Thread this state through recursive calls
  4. Update state based on the path taken (left vs right)

Complexity:

  • Time: O(n) - visit each node once
  • Space: O(h) - recursion depth equals tree height
  • State overhead: O(1) - just two values per recursive call

One-Sentence Core: BST validation requires inheriting and tightening ancestral constraints through recursion, not just checking local parent-child relationships.