Validate Binary Search Tree

MediumBST

Return true if a binary tree is a valid binary search tree, where every node sits within the value range allowed by its ancestors.

Open problem

Constraints

1 <= nodes <= 10^4
-2^31 <= Node.val <= 2^31 - 1

Range bounds recursion

Time O(n)Space O(h)

Carry an open interval (low, high) down the tree. Each node must lie strictly inside its interval; the left child tightens the upper bound and the right child the lower bound.

#include <bits/stdc++.h>
using namespace std;

struct TreeNode { int val; TreeNode* left; TreeNode* right; };

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

bool isValidBST(TreeNode* root) { return valid(root, LONG_MIN, LONG_MAX); }