98 - Validate Binary Search Tree

Difficulty: Medium | Pattern: Tree DFS with bounds | Company tags: Amazon, Google, Facebook, Microsoft

Problem Statement

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:

    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The root's right child (4) is less than root (5).

Common Mistake

Wrong approach: Only check root.left.val < root.val < root.right.val at each node. This fails for subtrees.

Counter-example: Tree [5, 4, 6, null, null, 3, 7]

    5
   / \
  4   6
     / \
    3   7

At node 6: 3 < 6 < 7 locally looks OK. But 3 is in the RIGHT subtree of 5, so 3 must be > 5. This tree is NOT a valid BST.

Correct Approach: Bounds Propagation

Pass down (min_val, max_val) bounds at each recursive call. The node value must be strictly within these bounds.

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

def isValidBST(root) -> bool:
    def validate(node, min_val, max_val):
        if not node:
            return True
        if node.val <= min_val or node.val >= max_val:
            return False
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

How bounds propagate:

• Going left: max_val becomes the parent's value (left child must be less than parent)
• Going right: min_val becomes the parent's value (right child must be greater than parent)

Algorithm Flow

Alternative: In-Order Traversal

A valid BST's in-order traversal (left → root → right) produces a strictly increasing sequence. Check that each value is greater than the previous.

def isValidBST(root) -> bool:
    prev = [float('-inf')]
    
    def inorder(node):
        if not node:
            return True
        if not inorder(node.left):
            return False
        if node.val <= prev[0]:
            return False
        prev[0] = node.val
        return inorder(node.right)
    
    return inorder(root)

Dry Run

Tree: 5 → right=4 (invalid for a BST)

• validate(5, -inf, +inf): 5 within range ✓
• validate(4, 5, +inf): 4 is less than or equal to min_val(5) → False ✓

Edge Cases

• Empty tree → valid BST
• Single node → valid BST
• Duplicate values: BST must be strict (no duplicates allowed in standard definition) — node.val <= min_val catches left-side duplicates; node.val >= max_val catches right-side
• Integer overflow: use float('-inf') and float('inf') as initial bounds (Python handles arbitrary-precision integers natively)

Complexity

Approach	Time	Space
Bounds propagation	O(n)	O(h)
In-order traversal	O(n)	O(h)

Where h = tree height; O(log n) for balanced BST, O(n) worst case.

Key Terms

Term	Definition
BST invariant	Every node's value must lie strictly between the min/max bounds inherited from its ancestors, not just its direct parent.
Bounds propagation	Passing (min_val, max_val) down the recursion so each subtree knows its valid range.
In-order traversal	Left → root → right visit order; produces a strictly increasing sequence for a valid BST.
Local vs. global check	Checking only left < node < right at one node (wrong) vs. checking against all ancestor bounds (correct).
Strict ordering	BSTs in this problem disallow duplicate values — comparisons use <=/>= to reject ties.

FAQ

1. Can this be solved without extra space? The bounds-propagation approach uses O(h) recursion stack space but no auxiliary data structure; a Morris in-order traversal can get in-order checking down to O(1) extra space at the cost of temporarily mutating tree pointers.
2. What if the tree is empty? An empty tree (root is None) is vacuously a valid BST, so validate returns True immediately.
3. How would this change if duplicate values were allowed on one side (e.g. <= on the left)? Swap the comparison to node.val < min_val (instead of <=) on whichever side should permit equal values, matching the problem's specific duplicate rule.
4. Why does checking only immediate children fail? A node deep in a subtree can violate an ancestor's constraint even though it satisfies its immediate parent — see the [5,4,6,null,null,3,7] counter-example in this page.
5. What if node values can be INT_MIN/INT_MAX? Use float('-inf')/float('inf') (or None sentinels in languages without native infinities) as initial bounds so real integer values can never falsely collide with the bound.

Quick Revision

• A valid BST requires every node to respect bounds from all ancestors, not just its parent.
• Wrong shortcut: checking only left.val < node.val < right.val locally.
• Correct fix: recursively pass (min_val, max_val) and shrink them on each left/right step.
• Going left tightens max_val to the parent's value; going right tightens min_val.
• Alternative approach: in-order traversal must yield strictly increasing values.
• Both approaches run in O(n) time and O(h) space (h = tree height).
• Edge cases: empty tree (valid), single node (valid), duplicate values (invalid — strict BST).
• Use float('-inf')/float('inf') as initial bounds to avoid overflow/sentinel bugs.

Related Problems

• 235 - Lowest Common Ancestor of a Binary Search Tree — same BST-bounds reasoning applied to ancestor search.
• 108 - Convert Sorted Array to Binary Search Tree — inverse construction problem using the same ordering invariant.
• 94 - Binary Tree Inorder Traversal — the traversal underlying the in-order validation approach.