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, minVal, maxVal)
├─ Check: minVal < node.val < maxVal
├─ Recurse left:  validate(node.left,  minVal,   node.val)  // inherit min, tighten max
└─ Recurse right: validate(node.right, node.val, maxVal)    // 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
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long minVal, long maxVal) {
    // Base case: empty tree is valid
    if (node == null) {
        return true;
    }

    // Check if current node violates constraints
    if (node.val <= minVal || node.val >= maxVal) {
        return false;
    }

    // Recursively validate subtrees with updated bounds
    boolean leftValid = validate(node.left, minVal, node.val);
    boolean rightValid = validate(node.right, node.val, maxVal);
    return leftValid && rightValid;
}

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
public boolean isValidBST(TreeNode root) {
    if (root == null) {
        return true;
    }

    // Check immediate children only
    if (root.left != null && root.left.val >= root.val) {
        return false;
    }
    if (root.right != null && root.right.val <= root.val) {
        return false;
    }

    // Recurse
    boolean leftValid = isValidBST(root.left);
    boolean rightValid = isValidBST(root.right);
    return leftValid && rightValid;
}

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 (node == null) {
    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 (node.val <= minVal || node.val >= maxVal) {
    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​

boolean leftValid = validate(node.left, minVal, node.val);   // left must be < node.val
boolean rightValid = validate(node.right, node.val, maxVal); // right must be > node.val
return leftValid && rightValid;  // Both subtrees must be valid

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
  • Return: Both subtrees must be valid for the whole tree to be valid

Complete Solution​

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public boolean isValidBST(TreeNode root) {
    return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean validate(TreeNode node, long minVal, long maxVal) {
    // Base case: empty tree is valid
    if (node == null) {
        return true;
    }

    // Check if current node violates constraints
    if (node.val <= minVal || node.val >= maxVal) {
        return false;
    }

    // Recursively validate subtrees with updated bounds
    boolean leftValid = validate(node.left, minVal, node.val);
    boolean rightValid = validate(node.right, node.val, maxVal);
    return leftValid && rightValid;
}

Edge Cases as Concept Validators​

Test Case 1: Single Node Tree [5]​

validate(node=5, min=Long.MIN_VALUE, max=Long.MAX_VALUE)
// Is Long.MIN_VALUE < 5 < Long.MAX_VALUE? 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=Long.MIN_VALUE, max=Long.MAX_VALUE)  // Root is valid
validate(left=2, min=Long.MIN_VALUE, max=2)   // Is Long.MIN_VALUE < 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, Long.MIN_VALUE, Long.MAX_VALUE)  // Valid, recurse left
validate(3, Long.MIN_VALUE, 5)               // Valid, recurse left
validate(1, Long.MIN_VALUE, 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, Long.MIN_VALUE, Long.MAX_VALUE)  // Root: MIN < 10 < MAX ✓
├─ validate(5, Long.MIN_VALUE, 10)            // Left of 10: MIN < 5 < 10 ✓
│  ├─ validate(2, Long.MIN_VALUE, 5)          // Left of 5: MIN < 2 < 5 ✓
│  └─ validate(7, 5, 10)                      // Right of 5: 5 < 7 < 10 ✓
└─ validate(15, 10, Long.MAX_VALUE)           // Right of 10: 10 < 15 < MAX ✓
   ├─ validate(12, 10, 15)                    // Left of 15: 10 < 12 < 15 ✓
   └─ validate(20, 15, Long.MAX_VALUE)        // Right of 15: 15 < 20 < MAX ✓

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 demonstrates two approaches to combining recursive boolean calls.

Approach 1: Explicit Boolean Variables (Recommended)

// Clear and debuggable
boolean leftValid = validate(node.left, minVal, node.val);
boolean rightValid = validate(node.right, node.val, maxVal);
return leftValid && rightValid;

Advantages:

  • Easy to debug (can inspect leftValid and rightValid separately)
  • Clear variable names document what each call validates
  • Both subtrees are always evaluated (no short-circuiting)

Approach 2: Inline Return with Short-Circuit

// More concise but evaluates lazily
return validate(node.left, minVal, node.val) &&
       validate(node.right, node.val, maxVal);

What's happening with short-circuit:

  1. Evaluate left subtree → returns true/false
  2. If left returns false, short-circuit and return false immediately (right subtree never evaluated)
  3. If left returns true, evaluate right subtree → returns true/false
  4. Return the combined result

Alternative: Full Evaluation with Early Returns

// Most verbose but very explicit
boolean leftValid = validate(node.left, minVal, node.val);
if (!leftValid) {
    return false;
}

boolean rightValid = validate(node.right, node.val, maxVal);
if (!rightValid) {
    return false;
}

return true;

All three work correctly! We use Approach 1 for clarity and debuggability.

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?"

public boolean hasPathSum(TreeNode root, int targetSum) {
    return dfs(root, targetSum);
}

private boolean dfs(TreeNode node, int remaining) {
    if (node == null) {
        return false;
    }

    // Leaf node check
    if (node.left == null && node.right == null) {
        return remaining == node.val;
    }

    // Recursive calls with updated remaining sum
    boolean leftPath = dfs(node.left, remaining - node.val);
    boolean rightPath = dfs(node.right, remaining - node.val);
    return leftPath || rightPath;
}

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"

private int maxSum;

public int maxPathSum(TreeNode root) {
    maxSum = Integer.MIN_VALUE;
    dfs(root);
    return maxSum;
}

private int dfs(TreeNode node) {
    if (node == null) {
        return 0;
    }

    // Only consider positive contributions
    int left = Math.max(0, dfs(node.left));
    int right = Math.max(0, dfs(node.right));

    // Update global max considering path through current node
    maxSum = Math.max(maxSum, node.val + left + right);

    // Return max path going through this node upward
    return node.val + Math.max(left, right);
}

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.