Binary Search Tree

Reader guide and study workflow · Complete course map

Start by trying to disprove a local rule

A root is 12, its right child is 20, and that child's left child is 9. Every edge points left to a smaller value or right to a larger value. Is the tree ordered correctly? List its inorder values: [12,9,20]. The failure is inherited from an ancestor: every node in the root's right subtree must exceed 12, even when it is a left child farther down.

A direct validator could collect each subtree's values and check all of them against every ancestor, repeating work on a tall tree. What information summarizes those constraints? All lower bounds reduce to their maximum, and all upper bounds to their minimum. At node 9, the permitted open interval is (12,20). Passing only these two bounds keeps every relevant obligation while discarding the history that generated it.

The interval is open because this pack's BSTs forbid duplicates. Numeric sentinels are safe only when they lie outside the allowed node domain. The reference has signed-32-bit values and int64 bounds; reusing the code for arbitrary int64 values would invalidate that choice.

Derive a stream instead of sorting again

For a tree already promised to be a valid BST, gather all values and sort them to find a rank. Now remove unnecessary work: the left subtree is already smaller than its root and the right is already larger. Inorder concatenates those sorted regions without a sorting step. For the kth value we can stop after k visits instead of storing all n values.

To suspend recursion, keep its pending ancestors on a stack. With root 9, left child 4, and 4's right child 6, construction leaves [9,4] from bottom to top. Popping 4 means 4 is visited; its right subtree contributes 6, giving [9,6]. Pushing is scheduling future work, not consuming a rank. An iterator is this paused computation made into an API. HasNext observes the pause; it must not advance it.

Ask which information can be thrown away

For sorted values [-8,-2,7,11], compare neighboring gaps 6,9,4. A nonadjacent gap is the sum of intervening nonnegative gaps, so it cannot improve on all of them. Only the previous value and the best gap must survive. This reduction relies on sorted order; taking adjacent values in an arbitrary traversal would be unjustified. A lazy stream saves result storage, but an unbalanced tree can still require O(n) pending ancestors.

Prerequisites and readiness

Know inorder traversal, strict ordering, open numeric bounds, and amortized cost. Distinguish a valid BST promise from the task of validating an arbitrary binary tree.

Reasoning workshop: order is inherited, not local

Ancestors keep imposing bounds

Root 10 with right child 15 and grandchild 6 as 15's left child passes a parent-only comparison: 6<15. It still violates the root's requirement that every value in its right subtree exceed 10. Pass an open interval of allowed values down the recursion. For that grandchild the interval is (10,15), so 6 is rejected. Strictness also rejects duplicate values. The reference's int64 sentinel bounds are outside the explicitly stated signed-32-bit node domain; they are not a universal strategy for arbitrary values of the same width as the sentinels.

Inorder turns structure into a sorted stream

For a valid BST, all left-subtree values precede the root, and all right-subtree values follow it. Inorder therefore visits ascending values. KthSmallest decrements its rank on a visit/pop, not while pushing a left spine. For values [1,3,4,8], rank 3 returns 4 after three visits. A valid rank is part of the precondition; returning a default zero for an invalid rank does not make it a supported query.

Minimum Difference needs only adjacent values in that sorted stream. For a<=b<=c, the gap c-a is the sum of the two adjacent gaps, so it cannot be smaller than both. Track the previous visited value with an explicit presence flag and compare each new neighbor pair. The two signed-32-bit endpoints can differ by 4294967295, which requires the 64-bit target even though each value is individually 32-bit.

An iterator is a suspended traversal

Construction pushes the initial left spine. Next pops the smallest pending node and pushes the left spine of its right subtree. HasNext merely checks whether a pending node exists; repeatedly calling it must not advance the iterator. Two iterators over one tree need separate frontiers and must not mutate the tree.

One Next can push O(h) nodes, so amortized O(1) does not mean every call has constant worst-case latency. Across a complete traversal, each node is pushed once and popped once, giving O(n) total work after accounting for construction. The stack holds at most a root-to-leaf frontier, O(h); on a skewed tree that may be O(n), not O(log n).

Reconstruct the assumptions before reusing the technique

A sorted inorder sequence can validate strict BST ordering, but KthSmallest and MinDiffInBST take a valid BST as a promise and exploit it. On an arbitrary tree, a numerically kth-smallest value would need a different algorithm. A lazy iterator can reduce output allocation but does not automatically improve worst-case tree height. For tests, create trees by insertion of unique values, compare iteration and ranks against an independently sorted list, and separately introduce ancestor-bound violations for the validator.

Reconstruction lab and answer key

Validate Binary Search Tree

A validator uses int64 minimum and maximum as exclusive sentinels. A new API allows node values across the full int64 range. Construct a valid tree it would reject and derive a bound representation that avoids the collision.

Model answer

A single node with value MinInt64 (or MaxInt64) is a valid BST, but it equals an exclusive sentinel and is rejected. Represent each bound with a presence flag (or optional value) and compare only present bounds. An inorder check with a previous-value presence flag also avoids fabricated endpoint values. The existing signed-32-bit contract makes the reference’s int64 sentinels safe.

Kth Smallest Element in a BST

A BST has root 10, left child 6 with children 2 and 8, and right leaf 14. For k=3, show the pending stack before each pop. Which actions consume a rank?

Model answer

Bottom-to-top stacks are [10,6,2], then [10,6], then [10,8]. The pops emit 2,6,8, so return 8 on the third pop. Popping 6 schedules its right child 8; this push does not consume rank. The remaining root 10 is pending below the smaller values until its left subtree is finished.

BST Iterator

An iterator has pending stack [10,3] bottom-to-top, and node 3 has right subtree rooted at 8 with left child 5. After Next, what value and stack result? What can two consecutive HasNext calls change?

Model answer

Next returns 3, pops it, and pushes 8 then 5, leaving [10,8,5]. The next returned value will be 5. HasNext can only report that the stack is nonempty; neither call may pop or push. This Next did several operations, which is compatible with amortized constant cost over a traversal.

Minimum Absolute Difference in BST

For sorted values [−8,−2,7,11], prove why comparing −8 directly with 7 cannot improve the current best adjacent gap. What must change if the input is an arbitrary binary tree?

Model answer

The adjacent gaps are 6,9,4; −8 to 7 spans 6+9=15, at least either intervening gap. Every nonadjacent difference similarly decomposes into nonnegative adjacent gaps, so some minimum pair is adjacent. Arbitrary-tree inorder is not sorted; collect and sort values or use another ordered structure before applying this proof.

Problems in this module

• Validate Binary Search Tree
• Kth Smallest Element in a BST
• BST Iterator
• Minimum Absolute Difference in BST

Interactive checkpoint

Open the Binary Search Tree quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable