Which ancestor still constrains this node?

Root 12 → right 20 → left 9.

A parent-only check accepts every edge. List inorder values and find the missing obligation.

What compact state preserves all ancestor obligations?

1 / 6

Validate Binary Search Tree — predict before coding

A node must satisfy constraints from all ancestors, not just its parent. Bounds are a compact representation of those inherited obligations.

Decision: Why is root 10 with right child 15 and that child’s left child 6 not a valid BST?

Presenter notes

Model answer: Although 6<15 satisfies its parent relationship, 6 lies in the right subtree of 10 and must also be greater than 10.

Correctness argument: For a recursive subtree with allowed open interval (lo,hi), every valid node must lie strictly within that interval. Reject a root outside it. For an accepted root value v, the entire left subtree must lie in (lo,v) and the entire right subtree in (v,hi); passing these intervals preserves both the current-node constraint and every ancestor constraint. Empty subtrees satisfy the condition. Structural induction proves that acceptance implies the strict ordering throughout the whole tree, and any valid BST satisfies every passed bound. The reference uses int64 sentinels outside the stated 32-bit value domain.

Debugging prompt: Test ancestor-bound violations, duplicate values, and 32-bit endpoint values. Strict comparisons reject duplicates. Numeric sentinels are safe here because node values are explicitly 32-bit, not arbitrary int64.

2 / 6

Kth Smallest Element in a BST — predict before coding

Inorder traversal turns strict BST order into rank order. A stack can pause that traversal after the kth visit instead of materializing every value.

Decision: In a BST whose inorder values are [1,3,4,8], how many pops identify k=3 and what value is returned?

3 / 6

BST Iterator — predict before coding

An iterator stores a suspended traversal, not a precomputed sorted array. Its stack is the frontier needed to produce exactly the next inorder value.

Decision: Can one Next call take O(h) work even though Next is described as amortized O(1)?

Presenter notes

Model answer: Yes. It may push a long left spine from a right subtree. Across the whole traversal each node is pushed and popped once, which gives the amortized bound.

Correctness argument: After construction, pushing the root's left spine puts the smallest node at the stack top. Before each Next, that top is the smallest unvisited node. Pop it and push the left spine of its right subtree; those nodes are the next candidates after the popped value, while older ancestors remain below them. This restores the frontier invariant. HasNext is true exactly when a candidate remains on the stack. Each tree node is pushed once and popped once over a full traversal, giving linear total work despite occasional Next calls pushing several nodes. Independent iterator instances retain independent frontiers.

Debugging prompt: Interleave two iterators over the same tree, repeat HasNext without consuming values, and exhaust an empty iterator without calling Next. The tree must remain unchanged.

4 / 6

Minimum Absolute Difference in BST — predict before coding

In a sorted sequence, a closest pair is adjacent. The BST supplies that sequence through inorder traversal, so only the previous value must be retained.

Decision: For inorder values [-5,-1,4,10], which pair gives the answer?

Presenter notes

Model answer: -5 and -1, with difference 4. No nonadjacent pair can be closer than every adjacent gap it spans.

Correctness argument: For any sorted values a<=b<=c, c-a=(b-a)+(c-b) is at least each adjacent gap. Thus a nonadjacent pair cannot improve on all gaps between its endpoints; some minimum pair is adjacent in sorted order. Inorder traversal of the valid BST visits values in that order. After the first visit, compare every new value with the previous one and keep the smallest gap. A separate previous-present flag avoids inventing a comparison before the first value. Every adjacent pair is considered exactly once, so the final minimum is the global minimum difference.

Debugging prompt: Test negative values and the two 32-bit endpoints; their difference can exceed signed 32-bit even though each node value fits it. The published at-least-two-nodes precondition makes a minimum pair exist.

5 / 6

An iterator is paused work

Root 7 has left leaf 1 and right child 11 with left leaf 9.

Draw the pending stack after construction and after each of the first two Next calls. Then change the task to repeated kth queries: what additional state might help?

6 / 6