Validate BST

Validating a BST

Given an arbitrary binary tree, how do you check if it satisfies the BST property?

A naive approach — checking that each node's left child is smaller and right child is larger — fails for this tree:

        5
       / \
      1   7
       \
        6    ← 6 > 5, but it's in the left subtree!

Each node must be greater than everything in its left subtree and less than everything in its right subtree.

The Min-Max Trick

Pass a valid range [min, max] down the tree. Each node's value must fall strictly within this range:

int is_bst(struct Node *root, int min, int max) {
    if (root == NULL) return 1;
    if (root->val <= min || root->val >= max) return 0;
    return is_bst(root->left, min, root->val)
        && is_bst(root->right, root->val, max);
}

Call with is_bst(root, -1000000, 1000000).

Going left narrows the upper bound to root->val. Going right narrows the lower bound. This propagates the full BST constraint down every path.

Your Task

Implement int is_bst(struct Node *root, int min, int max) that returns 1 if the subtree is a valid BST with all values in the range (min, max) exclusive, 0 otherwise.