Validate Binary Search Tree

How it works

A tree is a valid BST only if every node lies within a valid range defined by its ancestors.
Instead of using recursion, we can use a queue (BFS) to check this level by level.

• Start with the root, whose valid range is (-∞, +∞).
• When moving to the left child, its maximum allowed value becomes the current node’s value.
• When moving to the right child, its minimum allowed value becomes the current node’s value.
• If any node violates its allowed range, the tree is not a BST.

This way, we verify every node exactly once using BFS.

Steps

1. If the tree is empty → return true.
2. Push (root, -∞, +∞) into a queue.
3. While the queue is not empty:
   • Pop (node, leftBound, rightBound).
   • If node.val is not between (leftBound, rightBound), return false.
   • Push the left child with range (leftBound, node.val).
   • Push the right child with range (node.val, rightBound).
4. If all nodes satisfy their ranges → return true.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Only Comparing with the Immediate Parent

A classic mistake is checking only that left.val < node.val < right.val for direct children. This misses cases where a node deep in the left subtree has a value greater than an ancestor. For example, a tree with root 10, left child 5, and right grandchild 15 under node 5 would pass local checks but violates BST properties. The valid range must be inherited from all ancestors.

Using Inclusive Bounds Instead of Exclusive

BST properties require strictly less than and strictly greater than comparisons. Using <= or >= instead of < and > will incorrectly accept trees with duplicate values, which violates the standard BST definition where all left descendants are strictly less and all right descendants are strictly greater.

Integer Overflow with Boundary Values

When using Integer.MIN_VALUE and Integer.MAX_VALUE as initial bounds, problems arise if the tree contains these exact values as node data. The comparison node.val > Integer.MAX_VALUE will never be true. Use Long.MIN_VALUE and Long.MAX_VALUE or nullable types to handle edge cases where node values equal the integer limits.

from typing import Optional
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        q = deque([(root, float("-inf"), float("inf"))])

        while q:
            node, left, right = q.popleft()
            if not (left < node.val < right):
                return False
            if node.left:
                q.append((node.left, left, node.val))
            if node.right:
                q.append((node.right, node.val, right))

        return True

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root) {
            return true;
        }

        queue<tuple<TreeNode*, long, long>> queue;
        queue.push(make_tuple(root, LONG_MIN, LONG_MAX));

        while (!queue.empty()) {
            auto [node, left, right] = queue.front();
            queue.pop();

            if (!(left < node->val && node->val < right)) {
                return false;
            }
            if (node->left) {
                queue.push(make_tuple(node->left, left, node->val));
            }
            if (node->right) {
                queue.push(make_tuple(node->right, node->val, right));
            }
        }

        return true;
    }
};