∅
node
A binary tree is a BST when every node fits the strict ordering of all its ancestors, not just its parent. Carry an open (low, high) interval down each path and check every node against it.
Given a binary tree, return true iff it is a valid binary search tree: for every node, all values in its left subtree are strictly less and all values in its right subtree are strictly greater. [2,1,3] → true. The tree [5,1,4,null,null,3,6] → false: node 3 sits in the right subtree of 5, so it must exceed 5, but it doesn't.
(low, high) inherited from its ancestors. The root starts with (−∞, +∞). Going left tightens the upper bound to the parent's value; going right raises the lower bound to it. Thread those bounds down with DFS and every node validates itself in O(1).null subtree is a valid BST → return true.node.val <= low or node.val >= high, it breaks an ancestor's ordering → return false. Use strict bounds so duplicates fail.node.val: call dfs(left, low, node.val) — high tightens.node.val: call dfs(right, node.val, high) — low tightens.[5,1,4,null,null,3,6] the node 3 is a valid left child of 4 (3 < 4), yet the tree is invalid because 3 lives in 5's right subtree and must be greater than 5. Only the inherited (low, high) interval — not the immediate parent — catches this.Time is O(n) — one visit per node. Space is O(h) for the recursion stack, where h is the tree height: O(log n) when balanced, O(n) in the worst case (a degenerate chain).
(low, high). Root may be any value, so start with (−∞, +∞).// LeetCode 98 — Validate Binary Search Tree
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function isValidBST(root: TreeNode | null): boolean {
// Each node carries an OPEN interval (low, high) it must fall strictly inside.
const dfs = (
node: TreeNode | null,
low: number, // exclusive lower bound, -Infinity at root
high: number, // exclusive upper bound, +Infinity at root
): boolean => {
if (node === null) return true; // empty subtree is valid
if (node.val <= low || node.val >= high) // must be strictly within bounds
return false;
// Tighten the bound as we descend: left shrinks high, right raises low.
return (
dfs(node.left, low, node.val) &&
dfs(node.right, node.val, high)
);
};
return dfs(root, -Infinity, Infinity);
}dfs(node, low, high)asks: "is the subtree rooted here a valid BST whose every value falls strictly between low and high?" The bounds are exclusive.null node represents an empty subtree, which is trivially a valid BST → return true.node.val <= low || node.val >= high fails the node. Using <= / >= (not < / >) rejects duplicate values, which a strict BST forbids.(low, node.val) — the parent becomes the new ceiling. Right subtree inherits (node.val, high)— the parent becomes the new floor. This is exactly what propagates the "greater than every left-ancestor, less than every right-ancestor" constraint.dfs(root, -Infinity, Infinity). Using ±Infinity avoids special-casing the root or worrying about Number.MIN_SAFE_INTEGER edge values.[node, low, high] triples, or an iterative in-order walk tracking the previous value.Number.MIN_SAFE_INTEGER / MAX_SAFE_INTEGER without false failures.< / >= accordingly.| "is this tree a valid BST?" | DFS carrying (low, high) bounds |
| child looks fine vs parent but tree invalid | inherited ancestor bounds, not parent |
| going left in a BST | tighten high to node.val |
| going right in a BST | raise low to node.val |
function isValidBST(root: TreeNode | null): boolean {
const dfs = (node: TreeNode | null, low: number, high: number): boolean => {
if (!node) return true;
if (node.val <= low || node.val >= high) return false;
return dfs(node.left, low, node.val)
&& dfs(node.right, node.val, high);
};
return dfs(root, -Infinity, Infinity);
}(low, high) inherited from its ancestors: low < node.val < high.