Validate Binary Search Tree

Determine if a binary tree is a valid BST.

Pattern

Recursive Range Check

This problem follows the Recursive Range Check pattern, commonly found in the Trees category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Pass min/max bounds. Each node must be within bounds. Recurse with updated bounds.

Key Insight

Checking just parent-child isn't enough — a node must satisfy ALL ancestors. Passing bounds down ensures this globally.

Step-by-step

1Pass min and max bounds to each recursive call
2For the root, bounds are (-infinity, +infinity)
3For left child, update upper bound to parent's value
4For right child, update lower bound to parent's value
5If any node violates its bounds, return false

Pseudocode

def isValidBST(node, lo=-inf, hi=inf):
    if not node: return true
    if node.val <= lo or node.val >= hi:
        return false
    return isValidBST(node.left, lo, node.val) and isValidBST(node.right, node.val, hi)

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)

Master this pattern with YeetCode

Practice Validate Binary Search Tree and similar Trees problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Binary Tree Level Order Traversal NextBinary Tree Maximum Path Sum →