validate-bst.ts

import { TreeNode } from "../lib/tree-node.js";

/**
 * 98. Validate Binary Search Tree  (Medium)
 * Link: https://leetcode.com/problems/validate-binary-search-tree/
 *
 * Return true if the tree is a valid BST: every node's left subtree holds only
 * smaller values, its right subtree only larger values, and both subtrees are
 * themselves valid BSTs.
 *
 * Example:
 *   Input:  [2, 1, 3]      -> true
 *   Input:  [5, 1, 4, null, null, 3, 6] -> false  (4 is in 5's left subtree)
 *
 * Approach:
 *   DFS carrying an open (low, high) bound. Each node must lie strictly within
 *   its allowed range; going left tightens the upper bound to the node's value,
 *   going right tightens the lower bound. A local parent check alone is not
 *   enough — a value can violate an ancestor's bound.
 *
 * Time:  O(n)  — every node visited once.
 * Space: O(h)  — recursion stack.
 */
export function isValidBST(root: TreeNode | null): boolean {
  function validate(
    node: TreeNode | null,
    low: number,
    high: number,
  ): boolean {
    if (!node) return true;
    if (node.val <= low || node.val >= high) return false;
    return (
      validate(node.left, low, node.val) &&
      validate(node.right, node.val, high)
    );
  }

  return validate(root, -Infinity, Infinity);
}