Binary Search Trees

Binary Search Trees

Overview

Binary search trees are not mainly a recommendation to hand-roll pointer trees. They teach an ordered-set mindset: keep ordering separate from representation, treat height as the operational risk, make local navigation decisions from invariants, and use small pointer rewrites to preserve object identity while changing structure.

When applying this chapter in industrial contexts, answer both questions:

1. What invariant makes the operation correct?
2. What data-shape, identity, duplicate, cache, or library constraint makes the textbook implementation inappropriate or appropriate?

Shared CLRS Conventions

Also follow the parent clrs skill for mathematical formatting, theorem preconditions, proof tone, and chapter-skill routing. Put formal bounds in display LaTeX blocks, not inline prose.

When to Use

Use this skill for:

• Ordered dictionaries, ordered sets, range scans, predecessor and successor queries, nearest-neighbor-by-key questions, and sorted traversal.
• Basic BST operations: TREE-SEARCH, TREE-MINIMUM, TREE-MAXIMUM, TREE-SUCCESSOR, TREE-PREDECESSOR, TREE-INSERT, TREE-DELETE, and TRANSPLANT.
• Red-black-tree invariants, rotations, insertion fixup, deletion fixup, and height guarantees.
• Questions asking whether a plain BST, balanced BST, B-tree, skip list, hash table, array, or standard library container is the right production choice.
• Debugging pointer-tree code where the ordering relation is correct but parent links, external handles, rotations, or color/black-height repair are suspicious.

Do not use this skill as the primary guide for:

• Unordered exact lookup with no rank, range, predecessor, or sorted-order need; prefer hash-table reasoning.
• External-memory indexes, storage engines, or database indexes where B-trees or LSM-style structures dominate.
• Full sorting problems unless the point is to contrast inorder traversal with sorting or range enumeration.
• Implementing a production ordered map when the language standard library already provides one and no special invariant is required.

First Decision: What Ordered-Set Tool Fits?

BST Quick Reference

Always say that a BST operation costs proportional to height unless a balancing scheme is specified.

$$ O(h) $$

Inorder traversal visits every node once.

$$ \Theta(n) $$

The Core BST Invariant

State the ordering invariant before giving an operation or proof. For every node, keys in the left subtree are at most the node key, and keys in the right subtree are at least the node key. If duplicates are present, state the actual policy; the basic BST property permits equality on either side, but production code must choose a deterministic rule.

Good duplicate policies include:

• Store a count at one node when equal keys are indistinguishable.
• Store a list or bucket of records when one ordering key maps to multiple payloads.
• Use a compound key such as primary key plus stable tie-breaker when iteration must be deterministic.
• Route equals consistently left or right only for educational code, and still analyze the resulting height risk.

Height Is the Risk, Not the Operation List

Do not write that BST operations are logarithmic unless balance or input randomness is explicit. The correct analysis habit is:

1. Name the operation.
2. Say it follows one downward path, one upward parent-link path, or one traversal.
3. Bind the cost to tree height or node count.
4. Then explain what controls height.

Plain BSTs can be excellent as a concept and terrible as a service dependency. Random-ish insertion may give good average behavior, but sorted insertion, adversarial keys, or skewed duplicate routing can make the tree a chain.

Use this phrasing in production answers: "The textbook BST teaches the invariant and local operation. I would not deploy it directly unless input order and height are controlled; I would use a tested balanced ordered container or a cache-aware index."

Successor and Predecessor as Local Navigation

For successor and predecessor questions, avoid re-searching from the root unless the data structure lacks parent links. The chapter's insight is that sorted order is encoded locally:

• Right subtree exists: successor is the leftmost node in that right subtree.
• No right subtree: climb until the current node is in the left subtree of an ancestor; that ancestor is the successor.
• Predecessor is the mirror image.

This matters for industrial iteration because it turns "next item in sorted order" into a local operation on an iterator or node handle. Then check whether the implementation guarantees parent links, iterator validity after mutation, and duplicate ordering.

Deletion: Preserve Identity Before Optimizing Mechanics

Use TRANSPLANT as the conceptual boundary between "which node should occupy this position" and "how parent/child pointers are rewired." Deletion cases:

1. No left child: replace the deleted node by its right child.
2. No right child: replace the deleted node by its left child.
3. Two children: choose the successor, the minimum node in the right subtree, and move that successor node into the deleted node's position.

When the successor is not the deleted node's immediate right child:

1. Replace the successor by its own right child.
2. Give the successor the deleted node's right child.
3. Replace the deleted node by the successor.
4. Give the successor the deleted node's left child.

When the successor is the immediate right child, skip the first detach-and-reattach step for the right subtree.

The industrial lesson is stronger than the pseudocode: if external systems hold node pointers, iterators, locks, observers, cache entries, or identity-based handles, copying a successor's key and payload into the deleted node can make the wrong object appear to survive. The transplant-based deletion procedure moves nodes so the removed object is actually removed and the successor object remains itself.

Only copy keys or payloads when the API explicitly treats nodes as invisible storage cells and all external identity is by key/value, not by node object.

Red-Black Trees: Separate Order from Balance

A red-black tree is a BST plus color and black-height invariants. Keep two debugging tracks separate:

Red-black properties to preserve:

• Every node is red or black.
• The root is black.
• NIL leaves are black.
• Red nodes have black children.
• All simple paths from a node to descendant NIL leaves contain the same number of black nodes.

These properties imply logarithmic height.

$$ h \le 2\lg(n+1) $$

Rotations: Local Pointer Rewrite, Global Order Preserved

Use rotations as the key mental model for balanced trees: a rotation changes shape and heights without changing inorder order. It is a constant-time pointer rewrite around two adjacent nodes and three subtrees. Therefore:

• A rotation should not change the sorted sequence of keys.
• A rotation may change parent, child, root, and sentinel links.
• A red-black fixup combines rotations with recoloring to repair balance invariants after a normal BST insert or delete.

When explaining or debugging rotations, name the three ordered regions before and after the rotation. If their inorder concatenation is unchanged, the BST invariant survives; then verify colors and black heights separately.

Red-Black Insert and Delete Mindset

Insertion:

1. Insert as a normal BST leaf.
2. Color the new node red so black heights are initially unchanged.
3. Repair only possible violations: red root or red parent with red child.
4. If the uncle is red, recolor and move the red-red problem upward.
5. If the uncle is black, rotate and recolor to discharge the problem locally.

Deletion:

1. Do ordinary BST deletion while tracking the original color of the node actually removed from the tree.
2. If a red node was removed, black heights are unchanged.
3. If a black node was removed, model the replacement child as carrying an extra black deficit.
4. Use sibling cases to move the deficit upward, convert cases by rotation, or eliminate the deficit locally.

For production explanations, do not recite every case unless requested. Instead, state what each case is trying to preserve: order from the BST, no red-red edges, and equal black counts on all downward paths.

One Practical Design Pattern

When reviewing a proposed ordered-set implementation, use this checklist:

1. Operation need: Is there a real predecessor, successor, range, min/max, or sorted-iteration requirement?
2. Height control: Is balance guaranteed by the data structure, randomized enough for the risk, or absent?
3. Identity semantics: Are users holding node handles or iterators, and what happens after delete or rotation?
4. Duplicate policy: Are equal keys counted, bucketed, tie-broken, or routed consistently?
5. Memory behavior: Is pointer chasing acceptable, or would sorted arrays, B-trees, or library containers be faster and safer?
6. Mutation contract: Which operations invalidate iterators, parent links, cached extrema, or external indexes?

If any answer is vague, prefer a standard library or database/index structure over custom pointer-tree code.

Invariant and Proof Recipes

For BST operation correctness:

1. State the BST property and duplicate policy.
2. Identify the only path or local region the operation changes.
3. Show unchanged subtrees keep their relative order.
4. Show changed parent/child boundaries still separate lower keys from higher keys.
5. Conclude the invariant holds; then analyze height-dependent cost.

For rotations:

1. Name the left region, middle pivot relationship, and right region.
2. Show the inorder sequence is unchanged.
3. Check all parent/root/sentinel pointers affected by the local rewrite.
4. Only after order is preserved, analyze balance metadata.

For red-black height:

1. Use the red-node rule to argue at least every other node on a root-to-leaf path is black.
2. Use equal black count to relate path length to subtree size.
3. Conclude the height bound with the displayed inequality above.

RED Pressure Failures This Skill Prevents

Baseline agents usually know the textbook operations. This skill exists to prevent subtler failures:

• Saying "BST operations are logarithmic" without first proving or assuming height control.
• Treating BST deletion as just a key-copy trick and ignoring node identity, external handles, and payload mutation.
• Explaining red-black cases as memorized mechanics instead of separating order invariants from black-height repair.
• Recommending hand-rolled pointer trees when a standard ordered map, B-tree, skip list, sorted array, or hash table better matches production constraints.
• Omitting duplicate-key policy even though equality handling changes shape, iteration determinism, and worst-case height.
• Forgetting that rotations preserve inorder order but still must update parent, root, and sentinel links.

Common Mistakes

Verification Pressure Tests

Use these prompts to check whether this skill is working:

1. "A teammate says our plain BST map has logarithmic lookup because search halves the remaining tree. Correct them and recommend a production-safe alternative."
2. "We delete a node with two children by copying its successor's key and payload. What can go wrong if clients hold node handles? Give the transplant-based fix."
3. "A red-black-tree bug preserves sorted inorder traversal but violates black heights. How should we debug it?"
4. "Choose between hash table, plain BST, red-black tree, sorted array, and B-tree for a workload with exact lookup, range scans, duplicates, and cache-sensitive reads."
5. "Explain successor and predecessor without restarting search from the root, and state the parent-link assumption."

Static checks for this skill:

• SKILL.md lives at clrs/binary-search-trees/SKILL.md.
• Frontmatter name is binary-search-trees and description starts with Use when.
• The parent clrs skill lists this chapter skill.
• Formal bounds are displayed in LaTeX blocks, not embedded in prose.
• The text distinguishes textbook mechanics from production container choice.