Validate Binary Search Tree

medium Trees

Given the root of a binary tree, determine if it is a valid binary search tree. A valid BST requires that for every node, all values in its left subtree are strictly less than the node’s value, and all values in its right subtree are strictly greater. The tree can have between 1 and 10,000 nodes.

Example

Output: false

Node 4 is in the right subtree of 5, but 4 < 5. In a valid BST, every node in the right subtree must be greater than the root. Even though 4 < 7 satisfies the local parent-child rule, it violates the global BST property.

Pass a valid range (min, max) down through the recursion. The root can be anything, but its left child must be less than the root and its right child must be greater. At each node, check if the value falls within its allowed range, then recurse with tightened bounds.

Why this works

A BST is not just “left child < parent < right child” at each node — every node in the left subtree must be less than the root, and every node in the right subtree must be greater. By passing an allowed range (low, high) down the recursion and tightening it at each step, you enforce this global constraint without needing to look back up the tree.

Step by step

Start with infinite bounds — the root can be any value, so initialize with (-inf, +inf).
Check the current node — if its value is outside the allowed range (low, high), return false.
Recurse left with tighter upper bound — the left child must be less than the current node, so pass (low, node.val).
Recurse right with tighter lower bound — the right child must be greater than the current node, so pass (node.val, high).
Both subtrees must be valid — return true only if both recursive calls return true.

Time: O(n) Space: O(h)

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}


class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE); // start with no bounds
    }

    private boolean validate(TreeNode node, long low, long high) {
        if (node == null) {
            return true;
        }
        if (node.val <= low || node.val >= high) {
            return false; // node violates the allowed range
        }
        return validate(node.left, low, node.val) && // tighten upper bound for left subtree
               validate(node.right, node.val, high); // tighten lower bound for right subtree
    }
}

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};


class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return validate(root, LONG_MIN, LONG_MAX); // start with no bounds
    }

private:
    bool validate(TreeNode* node, long long low, long long high) {
        if (!node) {
            return true;
        }
        if (node->val <= low || node->val >= high) {
            return false; // node violates the allowed range
        }
        return validate(node->left, low, node->val) && // tighten upper bound for left subtree
               validate(node->right, node->val, high); // tighten lower bound for right subtree
    }
};

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


def isValidBST(root: TreeNode | None) -> bool:
    def validate(node, low, high):
        if not node:
            return True
        if node.val <= low or node.val >= high:
            return False  # node violates the allowed range
        return (validate(node.left, low, node.val) and  # left child must be < current
                validate(node.right, node.val, high))  # right child must be > current
    return validate(root, float('-inf'), float('inf'))  # start with no bounds