Validate Binary Search Tree

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

Examples

Example 1

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

Tree:
    2
   / \
  1   3

Valid BST: 1 < 2 < 3 ✓

Example 2

Input: root = [5,1,4,null,null,3,6]
Output: false

Tree:
      5
     / \
    1   4
       / \
      3   6

Invalid: Node 4 is in right subtree of 5, but 4 < 5 ✗

Example 3

Input: root = [5,4,6,null,null,3,7]
Output: false

Tree:
      5
     / \
    4   6
       / \
      3   7

Invalid: Node 3 is in right subtree of 5, but 3 < 5 ✗

Intuition

Common Mistake: Just checking left.val < node.val < right.val is NOT enough!

Example: [5,1,4,null,null,3,6] - Node 3 is in right subtree of 5 but 3 < 5.

Key Insight: Every node must satisfy a range constraint:

• Root: can be any value (-∞, +∞)
• Left child: must be in range (min, parent.val)
• Right child: must be in range (parent.val, max)

We pass down valid ranges and check if each node falls within its range.

Pattern Recognition

This is a DFS with Range Validation problem:

• Pass down min/max bounds
• Check if current node satisfies bounds
• Update bounds for children

Approach

DFS with Min/Max Bounds

1. Helper Function: isValid(node, min_val, max_val)

   • Returns True if subtree is valid BST within bounds

2. For Each Node:

   • Base case: null node is valid
   • Check if min_val < node.val < max_val
   • Validate left: isValid(left, min_val, node.val)
   • Validate right: isValid(right, node.val, max_val)

3. Initial Call: isValid(root, -∞, +∞)

Why this works:

• Bounds ensure ALL ancestor constraints are met
• Left child gets upper bound from parent
• Right child gets lower bound from parent
• Bounds propagate down the tree

In-order Traversal (Alternative)

BST property: In-order traversal produces sorted sequence!

def inorder(node):
  if not node: return True
  if not inorder(node.left): return False
  if node.val <= prev: return False
  prev = node.val
  return inorder(node.right)

If in-order is strictly increasing → valid BST

Edge Cases

• Empty tree (valid)
• Single node (valid)
• Duplicate values (invalid - must be strictly < or >)
• Integer overflow (use long or None for infinity)
• Negative values

Complexity Analysis

• Time: O(n) where n = number of nodes

  • Visit each node once
  • O(1) work per node

• Space: O(h) where h = height

  • Recursion stack
  • O(log n) for balanced tree
  • O(n) for skewed tree