Validate Binary Search Tree

medium bst tree recursion

Problem

Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key.

It isn't enough to compare a node only with its children — the BST property is global. Carry an inherited (lo, hi) open range down the recursion. The current node must lie strictly inside it; recurse left with hi = node.val and right with lo = node.val.

Inputlevel-order: [5, 1, 4, _, _, 3, 6]

Outputfalse

Node 3 sits in the right subtree of 5 yet is less than 5 — violates the inherited bound.

level-order ('_' for null)

def is_valid_bst(root):
    def ok(node, lo, hi):
        if node is None: return True
        if not (lo < node.val < hi): return False
        return ok(node.left, lo, node.val) and ok(node.right, node.val, hi)
    return ok(root, float("-inf"), float("inf"))

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

class Solution {
    public boolean isValidBST(TreeNode root) {
        return ok(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    boolean ok(TreeNode n, long lo, long hi) {
        if (n == null) return true;
        if (!(lo < n.val && n.val < hi)) return false;
        return ok(n.left, lo, n.val) && ok(n.right, n.val, hi);
    }
}

bool ok(TreeNode* n, long lo, long hi) {
    if (!n) return true;
    if (!(lo < n->val && n->val < hi)) return false;
    return ok(n->left, lo, n->val) && ok(n->right, n->val, hi);
}
bool isValidBST(TreeNode* root) { return ok(root, LONG_MIN, LONG_MAX); }

Explanation

The tempting mistake is to only compare a node with its two children, but the BST rule is global: every node in a left subtree must be smaller than all of its ancestors on that side. The fix is to carry an allowed range down the recursion.

The helper ok(node, lo, hi) requires the node's value to sit strictly inside the open interval (lo, hi). The root starts with (-inf, +inf) since anything is allowed there.

When we go left, the values must stay below the current node, so we tighten the upper bound: ok(node.left, lo, node.val). When we go right, they must stay above it, so we raise the lower bound: ok(node.right, node.val, hi). A node that escapes its inherited window fails the whole check.

Example: [5,1,4,_,_,3,6]. Node 4 is in 5's right subtree, so its allowed range becomes (5, +inf). Its child 3 must be above 5 but is not, so the check returns false.

Each node is validated once, so the algorithm runs in O(n).

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