Validate Binary Search Tree

LeetCode 98 • Medium • Trees

Inorder must be strictly increasing. Iterative: stack + prev; recursive: DFS with (min, max) bounds. Tree [5,1,4,null,null,3,6] is invalid (3 < 5).

TimeO(n)inorder visit each node

SpaceO(h)stack depth

prev: — Stack: —

Current node

Stack

Invalid

—

Stack

—

Speed:

Ready

Press Play. Inorder: push left, pop, check node > prev, push right. BST = strictly increasing inorder.

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

═══ VALIDATE BST — INORDER TRAVERSAL ═══

PATTERN ▸ Inorder (values strictly increasing) O(n) · O(h)

① INIT

stack, prev = [], None

② INORDER LOOP

while stack or root:

③ GO LEFT, PUSH

while root: stack.append(root); root = root.left

④ POP & CHECK

root = stack.pop()

if prev is not None and root.val <= prev: return False

⑤ UPDATE & GO RIGHT

prev = root.val

root = root.right

⑥ RETURN

return True

▼ your implementation ▼

Verify your solution: