Validate a Binary Search Tree

medium bst tree recursion

Problem

Decide whether a binary tree is a valid BST: every node's value must be strictly greater than every value in its left subtree and strictly less than every value in its right subtree.

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); }

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