Binary Search Tree

BSTs are ordered trees: inorder traversal yields a sorted sequence. Most BST problems reduce to this ordering plus careful boundary handling.

Pattern A: Validate BST with bounds

Use when: you must ensure all nodes obey strict ordering.

Invariant: each subtree has a valid (min, max) range.

Skeleton:

func valid(node, lo, hi):
    if node == nil: return true
    if node.val <= lo or node.val >= hi: return false
    return valid(node.left, lo, node.val) and valid(node.right, node.val, hi)

Problems:

• validate-binary-search-tree.

Pattern B: Inorder with a stack

Use when: you need kth smallest or a lazy iterator.

Invariant: stack holds the path to the next smallest node.

Skeleton (kth smallest):

stack = []
cur = root
while cur or stack not empty:
    while cur: push cur; cur = cur.left
    cur = pop
    k--
    if k == 0: return cur.val
    cur = cur.right

Skeleton (iterator):

pushLeft(root)
Next(): node = pop; pushLeft(node.right); return node.val

Problems:

• kth-smallest-element-in-a-bst.
• bst-iterator.

Pattern C: Inorder with prev tracking

Use when: you need min absolute difference or monotonic checks.

Invariant: inorder sequence is strictly increasing.

Skeleton:

prev = nil
best = +inf
inorder(node):
    if node == nil: return
    inorder(node.left)
    if prev != nil: best = min(best, node.val - prev)
    prev = node.val
    inorder(node.right)

Problems:

• minimum-absolute-difference-in-bst.

When to use BST properties (checklist)

• You need sorted-order traversal without extra sorting.
• Range constraints or k-th order statistics are involved.

Common failures (checklist)

• Using non-strict comparisons in validation.
• Forgetting that duplicates invalidate the BST in this pack.
• Not pushing the full left spine before reading a node.

Problem mapping

• validate-binary-search-tree: bounds recursion.
• kth-smallest-element-in-a-bst: inorder count.
• bst-iterator: explicit stack of left spine.
• minimum-absolute-difference-in-bst: inorder prev diff.