Validate Binary Search Tree

Approach Summary

Pass valid (min, max) range to each recursive call. Left child must be < node.val, right child must be > node.val.

Full Solution & Approach

A binary search tree requires that every node's value is greater than all values in its left subtree and less than all in its right subtree — not just its immediate children. Propagate a valid range down the recursion: the root accepts (-inf, +inf), the left child accepts (-inf, root.val), the right child accepts (root.val, +inf), and each level tightens the range on one side. If any node's value falls outside its allowed range, the tree is invalid. Using Python's float("-inf") and float("inf") as sentinels keeps the code clean and avoids null checks. An alternative in-order traversal trick — an inorder walk of a valid BST is strictly increasing — is also correct but the range-propagation version generalizes better to variants like "largest BST subtree". The recursive formulation costs O(h) stack space.

Every node is visited once — O(n) time. Recursion depth equals the tree height — O(h) space, worst case O(n) for a skewed tree.

Solution Code

Solution

def is_valid_bst(root) -> bool:
    def check(node, lo, hi):
        if not node:
            return True
        if not (lo < node.val < hi):
            return False
        return check(node.left, lo, node.val) and check(node.right, node.val, hi)
    return check(root, float('-inf'), float('inf'))

function isValidBST(root) {
  function check(node, lo, hi) {
    if (!node) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
  }
  return check(root, -Infinity, Infinity);
}

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

private boolean check(TreeNode node, long lo, long hi) {
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return check(node.left, lo, node.val) && check(node.right, node.val, hi);
}

bool isValidBST(TreeNode* root) {
    return check(root, LLONG_MIN, LLONG_MAX);
}

bool check(TreeNode* node, long long lo, long long hi) {
    if (!node) return true;
    if (node->val <= lo || node->val >= hi) return false;
    return check(node->left, lo, node->val) && check(node->right, node->val, hi);
}

Edge Cases to Watch

Empty tree — valid
A child equal to its parent — invalid per strict inequality
Integer boundaries — using infinity sentinels avoids off-by-one issues
A subtree that satisfies local checks but violates an ancestor range — caught by range propagation

How to Recognize This Pattern

Validate BST property
Range propagation

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(h)