214: Binary Search Trees, Balanced Trees, AVL/Red-Black Concepts, and Ordered Sets

Learning outcomes

By the end of this lesson, you can:

explain and apply bst invariant in a realistic implementation;
explain and apply search insert delete in a realistic implementation;
explain and apply degeneration in a realistic implementation;
explain and apply avl trees in a realistic implementation;
explain and apply red-black trees in a realistic implementation.

These outcomes are connected. The BST invariant gives you the ordering rule, search/insert/delete show how to use and preserve it, and degeneration exposes the cost of leaving height uncontrolled. AVL and red-black trees are two different ways to prevent that cost from dominating. Ordered sets then make the same ideas available through a higher-level collection API.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where you had to keep data ordered, find a boundary value, or deal with repeated updates. It might have involved an index, a sorted array, a queue of work, or a library map/set rather than a tree that you implemented yourself. The point is to connect the structure to a real requirement.

The goal is not to memorize terminology. It is to make a defensible decision in an interview-sized problem and in a production data-processing problem. Start with the constraints, then choose the structure whose guarantees match them. A tree that is theoretically suitable but allowed to become a long chain is not the same design as a tree whose height is actively controlled.

Terminology

BST invariant: For each node, keys in the left/right subtrees satisfy the chosen ordering rule. The rule must also say what happens to equal keys.
Search insert delete: Operations are O(h), where h is tree height. Treat this as a precise engineering concept, not merely vocabulary: the same operation can be O(log n) in a controlled tree and O(n) in a degenerate one.
Degeneration: Inserting sorted keys into an unbalanced BST can produce height n and O(n) operations. The structure still looks like a tree, but its useful behavior has collapsed into that of a linked list.
AVL trees: AVL trees maintain a strict height-balance invariant and use rotations after updates, providing O(log n) search/insert/delete with relatively aggressive balancing.
Red-black trees: Red-black trees use color/path invariants to keep height O(log n) with fewer rotations than stricter AVL balance, making them common in ordered map/set implementations.
Ordered operations: Balanced search trees support predecessor, successor, range iteration, floor/ceiling, and ordered traversal—capabilities hash tables do not provide efficiently.

The notation h matters. A tree operation follows one path from the root, so its running time is proportional to that path's length. If the tree has n nodes and height is logarithmic, the operation is logarithmic; if height has grown to roughly n, the same code has linear worst-case behavior.

Mental model

Treat Binary Search Trees, Balanced Trees, AVL/Red-Black Concepts, and Ordered Sets as a design problem with observable inputs, outputs, invariants, and failure modes. A BST is not just a collection of nodes with two child pointers. Its ordering invariant is what makes search possible. That invariant is useful only while the path to the relevant node remains acceptably short.

BSTs support ordered search when height is controlled. Worst-case degeneration explains why balanced trees and library ordered maps/sets exist. AVL and red-black trees do not remove the need to define comparison or duplicate behavior; they add rules that constrain shape after inserts and deletes. A strong implementation makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to prove why the design is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true. For example, ask whether callers need sorted iteration, predecessor/successor queries, or only membership checks. Decide whether duplicates represent multiple records, one record with an updated value, or invalid input. Then choose the mechanism that enforces those decisions instead of relying on an undocumented convention.

Deep dive

1. BST invariant

When a lookup needs to choose left or right, it depends on a stable ordering rule. For each node, keys in the left and right subtrees satisfy that rule. A common strict version is left < node < right, but an implementation may instead store duplicates consistently on one side or store a count at the node. Define duplicate handling explicitly; “duplicates go anywhere” breaks search and delete reasoning because the algorithm can no longer know where an equal key may be.

The comparison rule is part of the invariant too. If keys are compared case-insensitively during insertion but case-sensitively during lookup, the tree can appear structurally valid while searches behave incorrectly. The same comparator must be used consistently for every operation.

Decision rule: Use bst invariant deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. In production, document the comparator, duplicate policy, and whether mutation of a stored key is allowed. Mutating a key in place can invalidate the tree without changing a single child pointer.

2. Search insert delete

Search starts at the root and follows the comparison result until it finds the key or reaches an empty child. Insert follows the same path and places a new node at the first permitted empty position, or applies the chosen duplicate policy. Both operations are O(h), where h is tree height.

Deletion is where the invariant becomes more visible. A leaf can be removed directly. A node with one child can be replaced by that child. A node with two children is commonly replaced with its in-order successor, the smallest key in the right subtree, or its in-order predecessor, the largest key in the left subtree. After the replacement, remove the successor or predecessor from its original location and verify that the ordering rule still holds. Balanced implementations also update height or color metadata and may perform repairs.

Decision rule: Use search insert delete deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Write tests for root deletion, deleting a missing key, each child-count case, duplicates, and repeated updates. A return value such as “removed” versus “not found” should be part of the API contract rather than inferred from incidental tree state.

3. Degeneration

Inserting sorted keys into an unbalanced BST can produce height n and O(n) operations. Inserting 1, 2, 3, 4 with the usual strict comparison rule creates a chain leaning to the right; inserting the same values in descending order creates a chain leaning left. The ordering invariant has not been violated, but the height guarantee has disappeared.

Average behavior is not a worst-case guarantee. Random-looking input may keep a simple BST reasonably shallow, but a predictable input sequence, adversarial input, or a workload that becomes ordered over time can expose the linear path. This matters for latency as well as asymptotic analysis: one unusually deep operation can become a tail-latency problem.

Decision rule: Use degeneration deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Treat an unbalanced BST as appropriate only when its input constraints or workload make the height risk acceptable and observable. Otherwise, use a balancing strategy or an ordered collection with documented guarantees.

4. AVL trees

AVL trees maintain a strict height-balance invariant. At each node, the height difference between the left and right subtrees stays within the permitted bound, conventionally at most one. An insertion or deletion can make that difference invalid, so the implementation updates heights while walking back toward the root and applies a rotation when needed.

The four familiar repair shapes are left-left, right-right, left-right, and right-left. A single rotation handles the first two; a double rotation handles the latter two. The rotations change links, not the sorted sequence represented by the tree. With the invariant maintained, AVL search, insert, and delete are O(log n). AVL trees often keep the tree especially shallow, but they can perform more rebalancing work than a red-black tree, particularly across update-heavy workloads.

Decision rule: Use avl trees deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. AVL is a reasonable choice when lookup performance and a tight height bound matter, provided the implementation or library correctly handles metadata and deletion repairs. Do not claim that “balanced” means every operation takes exactly the same time; the guarantee is asymptotic, with constant factors and update costs still relevant.

5. Red-black trees

Red-black trees use a color assigned to each node and a set of path invariants to keep the height O(log n). The exact presentation varies, but the essential idea is that red nodes cannot be adjacent and that every path from a node to its missing-leaf boundaries has consistent black height. These restrictions prevent a path from becoming arbitrarily longer than another.

Insertion and deletion may recolor nodes and rotate subtrees. Compared with AVL trees, red-black trees permit a looser balance, usually requiring fewer rotations during updates while retaining logarithmic worst-case search, insert, and delete. This trade-off is one reason they are common in ordered map and set implementations. The implementation details are easy to get subtly wrong, so using a tested standard-library structure is often safer than maintaining a custom version without a strong reason.

Decision rule: Use red-black trees deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. When choosing a library ordered map/set, verify its guarantees, comparator behavior, duplicate semantics, memory characteristics, and iteration behavior instead of assuming every “ordered” collection uses the same tree or has the same complexity.

6. Ordered operations

Membership is only one reason to keep data ordered. A balanced search tree can find a predecessor or successor, iterate over a range, answer floor/ceiling queries, and produce sorted traversal without sorting the entire collection for every request. These operations are often O(log n) to locate a boundary, plus O(k) to visit k matching results, depending on the representation and API.

Hash tables are usually the better fit for direct membership or key-to-value lookup when ordering is not needed. They do not, in general, provide predecessor, successor, or efficient ordered range traversal. Choosing an ordered set solely because it “sounds more organized” adds costs that may not buy anything; choosing a hash table for a range-query requirement forces work somewhere else.

Decision rule: Use ordered operations deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State the operation mix before choosing a collection: point lookups, sorted iteration, range scans, updates, memory limits, and concurrency requirements all affect the decision.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. A small ordered-array helper makes the boundary behavior concrete before you implement a pointer-based tree. The following function returns the first index at which target could be inserted without breaking ascending order:

function lowerBound(nums: readonly number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid]! < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

This is binary search over a sorted array, not a BST implementation, but it demonstrates the same boundary-oriented reasoning. The active search interval is [lo, hi). At every iteration, the answer remains inside that interval. If the middle value is less than the target, the answer must be to its right, so lo advances. Otherwise, the middle position may itself be the answer, so hi moves left. The function returns an index in the inclusive range 0..nums.length; returning nums.length is correct when the target belongs after all existing values.

Under the precondition that nums is sorted according to the same ordering used by the comparison, the running time is O(log n) and the extra space is O(1). An empty array returns 0. Duplicate values return the first matching position, which is the “lower bound” policy. Without sorted input, the loop may still terminate but its result is not meaningful. That precondition is the equivalent of a BST invariant: the algorithm's decisions are valid only because the data has the expected order.

For a tree version, write the same contract before writing node links: decide whether equal keys are rejected, counted, or stored consistently; decide what “not found” returns; and decide whether the operation mutates the structure. Then walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. For an ordered structure, also ask whether the comparator is stable across versions, whether iteration can observe mutation, whether memory use is bounded, and whether worst-case latency is acceptable. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A balanced tree does not make malformed keys valid, does not provide authorization, and does not solve concurrent access by itself.

Guided lab

Implement a basic BST with an explicit duplicate policy and deletion. Construct a worst-case chain by inserting already sorted keys, measure or inspect its height, and then research and diagram the rotations or color invariants a balanced tree would use to keep height logarithmic. Your implementation should make the comparison rule visible and should let you distinguish a missing key from a successful deletion.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

For the inspection step, compare a sorted insertion sequence with an insertion order that produces a shallower tree, then verify search and deletion after rotations or structural changes. The goal is not to build a production-ready balancing library in one lab. It is to connect the invariant, the measured height, the operation cost, and the reason a tested ordered collection may be the safer production choice.

Edge cases and failure modes

BST invariant: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include inconsistent comparisons and key mutation if the API permits either.
Search insert delete: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Cover an empty tree, root deletion, leaf deletion, one-child deletion, and two-child deletion.
Degeneration: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include sorted and reverse-sorted insertion, because average-case measurements can hide the worst case.
AVL trees: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Exercise all four rotation shapes and verify stored heights after insertions and deletions.
Red-black trees: test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify the color/path invariants after recoloring, rotations, root changes, and deletion repair.

When a failure appears, inspect the first operation that makes an invariant false, not only the later lookup that exposes it. A failed ordering check points toward comparisons or link updates. A failed height or color check points toward metadata maintenance or repair logic. A sudden linear latency pattern points toward height growth, input distribution, or a collection whose guarantee was misunderstood.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual value or execution plan, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. For a tree, print or visualize each node's key, child links, height, and color metadata where applicable. Compare an in-order traversal with the expected sorted sequence; then check height and balancing rules independently. A correct traversal alone does not prove that an AVL or red-black implementation maintained its stronger invariant.

Interview questions

What problem does BST invariant solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Search insert delete solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Degeneration solve, and what trade-off or failure mode would make you choose a different approach?
What problem does AVL trees solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Red-black trees solve, and what trade-off or failure mode would make you choose a different approach?

When answering, include the invariant and the relevant height, not just the name of a structure. A strong answer distinguishes the ordinary BST's O(h) bound from the O(log n) worst-case bound of a properly balanced tree, and it explains why the operation mix might favor AVL, red-black, hashing, or a sorted array.

Checkpoint

Without notes, explain Binary Search Trees, Balanced Trees, AVL/Red-Black Concepts, and Ordered Sets to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code. Be prepared to state the duplicate policy, the height assumption, and the complexity of each operation you expose.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.