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 (LeetCode 98) ───

# Pattern: Inorder traversal — values must be strictly increasing

# Time: O(n) Space: O(h)

# 1. Define: isValidBST(root)

# 2. Init stack and prev:

# stack, prev = [], None

# 3. Iterative inorder: while stack or root:

# 4. Go left, push: while root: stack.append(root); root = root.left

# 5. Pop and check: root = stack.pop()

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

# 6. Update prev, go right: prev = root.val; root = root.right

# 7. All valid: return True

# Vars: stack, prev, root

▼ your implementation ▼

Verify your solution: