98. Validate Binary Search Tree

Return true if the binary tree is a valid binary search tree: every left subtree holds smaller values, every right subtree holds larger values, recursively.

An in-order walk of a BST visits values in strictly increasing order. Walk iteratively with a stack and compare each value with the previous one.

1function isValidBST(root: TreeNode | null): boolean {
2  const stack: TreeNode[] = [];
3  let n = root, prev = -Infinity;
4  while (n || stack.length) {
5    while (n) { stack.push(n); n = n.left; }
6    n = stack.pop()!;
7    if (n.val <= prev) return false;
8    prev = n.val;
9    n = n.right;
10  }
11  return true;
12}

prev = -∞

tree

in-order so far

empty

stack

empty

Start at the root.

1 / 0

Space: play/pause · ←/→: step