Validate Binary Search Tree

Difficulty: Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree
Link: https://leetcode.com/problems/validate-binary-search-tree/

Problem Description

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

A valid BST is defined as follows:

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 the left and right subtrees must also be binary search trees.

Example 1:


Input: root = [2,1,3]
Output: true

Example 2:


Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

Constraints:

The number of nodes in the tree is in the range [1, 104].
-231 <= Node.val <= 231 - 1

Solution

1. Problem Deconstruction

Technical Definition

Given the root node of a binary tree, algorithmically verify that every node satisfies the BST invariant:

For any node ( u ), all nodes ( v ) in its left subtree must satisfy ( v.val < u.val )
For any node ( u ), all nodes ( w ) in its right subtree must satisfy ( w.val > u.val )
Recursively, all subtrees rooted at ( u.left ) and ( u.right ) must also be BSTs.

Beginner-Friendly Explanation

Imagine organizing books on a shelf where each book has a unique number. The rule is:

Books to the left of a chosen book must have smaller numbers.
Books to the right must have larger numbers.
Every subsection of the shelf must follow the same rule.
Your task is to check if the entire shelf follows these rules.

Mathematical Formulation

Let ( T ) be a binary tree. Define:

( \text{left}(u) ): Left subtree of node ( u )
( \text{right}(u) ): Right subtree of node ( u )
( \text{val}(u) ): Value of node ( u )
( \min(S) ), ( \max(S) ): Min/max values in subtree ( S )

( T ) is a BST iff ( \forall u \in T ):

\begin{cases} \max(\text{left}(u)) < \text{val}(u) & \text{if } \text{left}(u) \text{ exists} \\ \min(\text{right}(u)) > \text{val}(u) & \text{if } \text{right}(u) \text{ exists} \\ \text{left}(u) \text{ is BST} \\ \text{right}(u) \text{ is BST} \end{cases}

Constraint Analysis

Node count ( \in [1, 10^4] ):
- Rules out ( O(n^2) ) solutions (e.g., brute-force subtree min/max checks).
- Mandates ( O(n) ) or ( O(n \log n) ) algorithms.
- Edge: Worst-case skewed trees (linked lists) require iterative traversal to avoid stack overflow.
Node values ( \in [-2^{31}, 2^{31} - 1] ):
- Initial bounds must handle extreme values (e.g., use ( -\infty )/( \infty ) or nullable bounds).
- Edge: Values at ( -2^{31} ) or ( 2^{31}-1 ) must not cause integer overflow in bounds checks.
Strict inequalities:
- Duplicate values immediately invalidate the BST.
- Edge: Parent-child equality (e.g., [2,2]) must return false.

2. Intuition Scaffolding

Analogies

Real-World Metaphor (Corporate Hierarchy):
CEO (root) requires all left-department salaries ( < ) theirs and right-department salaries ( > ) theirs. Each department head enforces identical rules recursively.
Gaming Analogy (Dungeon Crawl):
Each room (node) contains a key. To move left, you need a key ( < ) current room’s key; to move right, ( > ). The dungeon is valid only if all paths obey this.
Math Analogy (Strictly Increasing Sequence):
An in-order traversal of a BST is equivalent to generating a sorted list. Verification reduces to checking ( a_i < a_{i+1} ) for all elements.

Common Pitfalls

Shallow Child Checks:
Only verifying immediate children (e.g., root.val > root.left.val) misses deeper violations (e.g., grandchild ( > ) root).
Global Min/Max Misuse:
Assuming the global minimum/maximum of the tree defines bounds for all subtrees (ignores local subtree constraints).
Duplicate Blindness:
Overlooking strict inequalities (e.g., left.val == root.val is invalid).
Boundary Corruption:
Incorrectly propagating bounds (e.g., updating upper bound with node.val when traversing right).
Integer Overflow:
Using INT_MIN/INT_MAX as initial bounds when node values can be these extremes.

3. Approach Encyclopedia

Brute Force: Subtree Min/Max Validation

Idea: For each node, recursively find min/max of left/right subtrees and verify against node.val.

Pseudocode:

def isBST(node):
    if not node: 
        return (True, None, None)  # (valid, min, max)
    
    left = isBST(node.left)
    right = isBST(node.right)
    
    valid = (
        left[0] and right[0] and
        (not node.left or left[2] < node.val) and
        (not node.right or right[1] > node.val)
    )
    min_val = left[1] if node.left else node.val
    max_val = right[2] if node.right else node.val
    return (valid, min_val, max_val)

Complexity:
- Time: ( O(n^2) ) worst-case (each node triggers min/max scans of subtrees).
- Space: ( O(n) ) for recursion stack.

Visualization:

Tree: [5,1,4,null,null,3,6]
Check root=5:
  Left subtree (1): min=1, max=1 → 1<5 ✓
  Right subtree (4): min=3, max=6 → 3<5 ✗ (invalid)

Optimal 1: Recursive Traversal with Bounds

Idea: Propagate allowable (low, high) bounds during DFS.

Pseudocode:

def validate(node, low, high):
    if not node: return True
    if node.val <= low or node.val >= high: 
        return False
    return (
        validate(node.left, low, node.val) and 
        validate(node.right, node.val, high)
    )

Complexity:
- Time: ( O(n) ) (each node visited once).
- Space: ( O(h) ), where ( h ) is tree height (( O(n) ) worst for skewed trees).

Visualization:

Tree: [2,1,3] 
  Root(2): (-∞, ∞)
    Left(1): (-∞, 2) → valid
    Right(3): (2, ∞) → valid

Optimal 2: Iterative In-order Traversal

Idea: In-order traversal must yield strictly increasing values.

Pseudocode:

stack, prev = [], None
curr = root
while curr or stack:
    while curr:
        stack.append(curr)
        curr = curr.left
    curr = stack.pop()
    if prev and curr.val <= prev: 
        return False
    prev = curr.val
    curr = curr.right
return True

Complexity:
- Time: ( O(n) ) (each node pushed/poped once).
- Space: ( O(h) ) (stack stores current path).

Visualization:

Tree: [5,1,4,null,null,3,6] 
In-order: 1 → 5 → 3 → ✗ (3 < 5 → invalid)

Optimal 3: Iterative Bounds (DFS)

Idea: Simulate recursive bounds using a stack.

Pseudocode:

stack = [(root, -∞, ∞)]
while stack:
    node, low, high = stack.pop()
    if node.val <= low or node.val >= high: 
        return False
    if node.left: 
        stack.append((node.left, low, node.val))
    if node.right: 
        stack.append((node.right, node.val, high))
return True

Complexity:
- Time: ( O(n) ).
- Space: ( O(n) ) (worst-case for skewed trees).

Visualization:

Tree: [5,1,4,null,null,3,6]
  Root(5): (-∞, ∞)
    Left(1): (-∞, 5) → valid
    Right(4): (5, ∞) → 4 ≤ 5 ✗

4. Code Deep Dive

Optimal Solution: Iterative In-order (Python)

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack, prev = [], None  # Use None for initial prev (no prior value)
        curr = root
        
        while curr or stack:
            # Traverse to deepest left
            while curr:
                stack.append(curr)
                curr = curr.left
            # Visit current node
            curr = stack.pop()
            # Check order invariant (prev must be < curr)
            if prev is not None and curr.val <= prev:
                return False
            prev = curr.val  # Update prev for next node
            # Move to right subtree
            curr = curr.right
        
        return True

Line-by-Line Annotations

stack, prev = [], None:
- stack: LIFO structure for DFS backtracking.
- prev: Tracks last visited node’s value (initialized to None for the first node).
while curr or stack:
- Continues until all nodes are processed (stack empty and curr is None).
Nested while curr:
- Pushes all leftmost nodes to stack (builds path to deepest left).
curr = stack.pop():
- Pops the deepest left node (in-order visit).
if prev is not None and curr.val <= prev:
- Edge Handling:
  - prev is None: Skip check for first node (no predecessor).
  - curr.val <= prev: Violates BST (strict increase required).
  - Example 2: Fails at 3 <= 5 (prev=5 after root).
prev = curr.val:
- Updates predecessor for next in-order node.
curr = curr.right:
- Moves to right subtree (in-order traversal rule).

5. Complexity War Room

Hardware-Aware Analysis

Memory: At ( n=10^4 ) nodes:
- Recursive Bounds: Stack depth ( \approx 10^4 ). Python recursion limit (~1000) may require sys.setrecursionlimit (not recommended).
- Iterative In-order: Stack uses ( \approx 10^4 ) pointers (80KB in Python) — fits in L2/L3 cache.
Speed: ( O(n) ) traversal is optimal; cache-friendly for iterative DFS (sequential access).

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	(O(n^2))	(O(n))	7/10	❌ (Fails (n=10^4))
Recursive Bounds	(O(n))	(O(n))	9/10	✅ (If depth < 1k)
Iterative In-order	(O(n))	(O(n))	8/10	✅ (Always safe)
Iterative Bounds (DFS)	(O(n))	(O(n))	7/10	✅ (BFS alternative)

6. Pro Mode Extras

Variants

LC 99 (Recover BST):
- Use in-order traversal to detect/fix two swapped nodes.
LC 333 (Largest BST Subtree):
- Track (min, max, size, is_bst) per subtree during DFS.
LC 255 (Verify Preorder):
- Validate BST preorder sequence without building the tree (use monotonic stack).
k Transactions (LC 123):
- Extend to constrained buys/sells (DP with states).

Interview Cheat Sheet

First Mention: Always state time/space complexity upfront.
Clarify: Duplicates? (Always invalid.)
Default Choice: Iterative in-order (avoids recursion issues).
Edge Arsenal:
- Single node → valid.
- Skewed trees → test iterative solutions.
- Duplicates/equality → immediate fail.
- -2^31/2^31-1 → use float('inf') for bounds.

#98 - Validate Binary Search Tree

Validate Binary Search Tree

Problem Description

Solution

1. Problem Deconstruction

Technical Definition

Beginner-Friendly Explanation

Mathematical Formulation

Constraint Analysis

2. Intuition Scaffolding

Analogies

Common Pitfalls

3. Approach Encyclopedia

Brute Force: Subtree Min/Max Validation

Optimal 1: Recursive Traversal with Bounds

Optimal 2: Iterative In-order Traversal

Optimal 3: Iterative Bounds (DFS)

4. Code Deep Dive

Optimal Solution: Iterative In-order (Python)

Line-by-Line Annotations

5. Complexity War Room

Hardware-Aware Analysis

Industry Comparison Table

6. Pro Mode Extras

Variants

Interview Cheat Sheet