Red-Black Tree: Complete Implementation Guide

1. Introduction and Core Concepts

A red-black tree is a self-balancing binary search tree (BST) that guarantees logarithmic time complexity for core operations by enforcing a set of coloring constraints on each node. Every node is colored either red or black, and these colors are used to ensure that no path from the root to a leaf is more than twice as long as any other path. This approximate balancing avoids the degenerate worst-case of a standard BST, which can degrade into a linked list with O(n) operations when keys are inserted in sorted order.

The red-black tree was invented by Rudolf Bayer in 1972 as the "symmetric binary B-tree" and later popularized by Leo Guibas and Robert Sedgewick, who introduced the red-black color convention. It provides a practical trade-off between strict balancing and insertion/deletion cost, which is why it has become the default balanced BST in many language standard libraries, including Java's TreeMap, C++ STL's std::map and std::set, and the Linux kernel's Completely Fair Scheduler.

Unlike perfectly balanced trees, a red-black tree does not guarantee minimal height. Instead, it guarantees that the longest root-to-leaf path is at most twice the shortest, which is sufficient to keep height bounded by O(log n). This relaxed invariant makes rebalancing cheaper than in more rigid structures like AVL trees, requiring fewer rotations on average during updates.

The Five Invariants

Every red-black tree must satisfy five properties to maintain its guarantees:

• 1. Node Color: Every node is either red or black.
• 2. Root Property: The root is always black.
• 3. Red Property: Red nodes cannot have red children (no two red nodes can be adjacent). This is also called the "no double red" rule.
• 4. Black Height Property: Every path from a given node to any of its descendant NIL leaves contains the same number of black nodes. This number is called the black-height.
• 5. NIL Leaves Property: All leaves (NIL or null children) are black. In implementations, these are often represented by a single sentinel NIL node.

When these invariants are violated after an insertion or deletion, the tree restores them through two fundamental operations: recoloring and rotation. Understanding these invariants is essential because every fix-up procedure is simply a systematic way to restore them without violating the binary search tree ordering property.

2. How It Works

A red-black tree maintains balance not by storing heights or balance factors, but by controlling the distribution of red and black nodes. The black-height property ensures that the tree is bushy and shallow. If a tree has black-height bh, it contains at least 2^bh - 1 internal black nodes, which implies the height h is at most 2 * log2(n+1). This logarithmic bound is the foundation of its performance guarantee.

The core balancing mechanisms are left rotation, right rotation, and recoloring. A rotation is a local operation that preserves BST ordering while changing the parent-child relationships to reduce height. Recoloring simply flips a node's color from red to black or vice versa to fix violations of the black-height or red property. Most insertions and deletions require only O(1) rotations and O(log n) recolorings.

During insertion, the new node is always inserted as a red node using standard BST insertion. Coloring it red avoids violating the black-height property, but it may create a double-red violation if its parent is also red. The insertion fix-up then handles this violation by examining the color of the node's uncle (the sibling of its parent). Depending on the uncle's color and the node's position, the algorithm applies one of several cases involving recoloring or rotations.

Insertion Fix-Up Cases

Let z be the newly inserted red node, p be its parent, g be its grandparent, and u be its uncle. The fix-up proceeds while p is red:

• Case 1 - Uncle is Red: Recolor p and u to black, and g to red. Then move z up to g and continue. This case propagates the double-red problem upward but preserves black-height.
• Case 2 - Uncle is Black and z is a Triangle: If z is a right child and p is a left child (or vice versa), perform a rotation on p to convert it into Case 3. For example, if p is left child of g and z is right child of p, do a left rotation on p.
• Case 3 - Uncle is Black and z is a Line: If z and p are both left children or both right children, recolor p to black and g to red, then rotate g in the opposite direction of p. This terminates the fix-up.

Deletion is more complex because removing a black node violates the black-height property, creating a "double-black" deficit on one path. The deletion fix-up restores balance by borrowing black height from a sibling subtree through rotations and recolorings. It examines the sibling's color and the colors of the sibling's children to determine the correct transformation.

Rotations Explained

A left rotation on node x assumes x has a right child y. It makes y the new parent of x, moves y's left subtree to become x's right subtree, and updates parent pointers. A right rotation is symmetric. Rotations are O(1) pointer manipulations and do not affect the inorder traversal order, so the BST property is preserved. In a red-black tree, rotations are always combined with recoloring to maintain all five invariants.

3. Implementation

Implementing a red-black tree correctly requires careful handling of parent pointers, the sentinel NIL node, and the fix-up procedures. Using a single shared NIL sentinel for all leaves simplifies boundary checks and ensures the leaf property is consistently enforced. Below is a complete, production-quality Python implementation broken into modular parts.

The first block defines the node structure and tree initialization. We use a sentinel NIL node that is always black to avoid null checks throughout the code. This pattern mirrors implementations in CLRS (Introduction to Algorithms) and reduces bugs related to None handling.

class Color:
    RED = 0
    BLACK = 1

class RBNode:
    def __init__(self, key=None, color=Color.BLACK):
        self.key = key
        self.color = color
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        # Sentinel NIL node - single shared black leaf
        self.NIL = RBNode(color=Color.BLACK)
        self.NIL.left = self.NIL
        self.NIL.right = self.NIL
        self.NIL.parent = self.NIL
        self.root = self.NIL

    def _is_red(self, node):
        return node.color == Color.RED

    def _is_black(self, node):
        return node.color == Color.BLACK

The second block implements the two primitive rotations. These operations must correctly update four sets of pointers: child links, parent links, the root pointer if the rotated node was the root, and the subtree that moves between nodes. A common mistake is forgetting to update the parent of the moved subtree.

    def left_rotate(self, x):
        # Assumes x.right != NIL
        y = x.right
        # Turn y's left subtree into x's right subtree
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        # Link x's parent to y
        y.parent = x.parent
        if x.parent == self.NIL:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        # Put x on y's left
        y.left = x
        x.parent = y

    def right_rotate(self, y):
        # Symmetric to left_rotate
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent == self.NIL:
            self.root = x
        elif y == y.parent.right:
            y.parent.right = x
        else:
            y.parent.left = x
        x.right = y
        y.parent = x

The third block handles BST insertion followed by the red-black fix-up. The insertion itself is standard BST logic, but we initialize the new node as red with NIL children. The fix-up loop then restores invariants using the three cases described earlier. Note the use of < and > comparisons that must be escaped in HTML rendering.

    def insert(self, key):
        z = RBNode(key=key, color=Color.RED)
        z.left = self.NIL
        z.right = self.NIL

        y = self.NIL
        x = self.root
        # Standard BST insert
        while x != self.NIL:
            y = x
            if z.key < x.key:
                x = x.left
            elif z.key > x.key:
                x = x.right
            else:
                return  # Duplicate keys not allowed

        z.parent = y
        if y == self.NIL:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

        self._insert_fixup(z)

    def _insert_fixup(self, z):
        while self._is_red(z.parent):
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right  # uncle
                if self._is_red(y):
                    # Case 1: uncle is red - recolor
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z == z.parent.right:
                        # Case 2: triangle - left rotate
                        z = z.parent
                        self.left_rotate(z)
                    # Case 3: line - recolor and right rotate
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self.right_rotate(z.parent.parent)
            else:
                # Symmetric case for right side
                y = z.parent.parent.left
                if self._is_red(y):
                    z.parent.color = Color.BLACK
                    y.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = Color.BLACK
                    z.parent.parent.color = Color.RED
                    self.left_rotate(z.parent.parent)
        self.root.color = Color.BLACK

The final block implements deletion, search, and traversal. Deletion uses the classic transplant helper to replace one subtree with another. If the deleted node was black, we must fix the double-black violation. The search and inorder traversal demonstrate that the tree still behaves as an ordered dictionary.

    def transplant(self, u, v):
        if u.parent == self.NIL:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent

    def delete(self, key):
        z = self.search(key)
        if z == self.NIL:
            return False
        y = z
        y_original_color = y.color
        if z.left == self.NIL:
            x = z.right
            self.transplant(z, z.right)
        elif z.right == self.NIL:
            x = z.left
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                self.transplant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transplant(z, y)
            y.left = z.left
            y.left.parent = y
            y.color = z.color
        if y_original_color == Color.BLACK:
            self._delete_fixup(x)
        return True

    def _delete_fixup(self, x):
        while x != self.root and self._is_black(x):
            if x == x.parent.left:
                w = x.parent.right
                if self._is_red(w):
                    w.color = Color.BLACK
                    x.parent.color = Color.RED
                    self.left_rotate(x.parent)
                    w = x.parent.right
                if self._is_black(w.left) and self._is_black(w.right):
                    w.color = Color.RED
                    x = x.parent
                else:
                    if self._is_black(w.right):
                        w.left.color = Color.BLACK
                        w.color = Color.RED
                        self.right_rotate(w)
                        w = x.parent.right
                    w.color = x.parent.color
                    x.parent.color = Color.BLACK
                    w.right.color = Color.BLACK
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                # Symmetric with left/right swapped
                w = x.parent.left
                if self._is_red(w):
                    w.color = Color.BLACK
                    x.parent.color = Color.RED
                    self.right_rotate(x.parent)
                    w = x.parent.left
                if self._is_black(w.right) and self._is_black(w.left):
                    w.color = Color.RED
                    x = x.parent
                else:
                    if self._is_black(w.left):
                        w.right.color = Color.BLACK
                        w.color = Color.RED
                        self.left_rotate(w)
                        w = x.parent.left
                    w.color = x.parent.color
                    x.parent.color = Color.BLACK
                    w.left.color = Color.BLACK
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = Color.BLACK

    def search(self, key):
        curr = self.root
        while curr != self.NIL and key != curr.key:
            if key < curr.key:
                curr = curr.left
            else:
                curr = curr.right
        return curr

    def minimum(self, node):
        while node.left != self.NIL:
            node = node.left
        return node

    def inorder(self):
        result = []
        def _walk(n):
            if n != self.NIL:
                _walk(n.left)
                result.append((n.key, "R" if n.color==Color.RED else "B"))
                _walk(n.right)
        _walk(self.root)
        return result

4. Step-by-Step Example

To make the abstract fix-up rules concrete, let us walk through inserting the sequence [10, 18, 7, 15, 16] into an initially empty red-black tree. This sequence is chosen because it triggers all three insertion cases and requires both recoloring and rotations.

We start with an empty tree where root = NIL. Insert 10: Since the tree is empty, 10 becomes the root and is colored black to satisfy the root property. The tree now has black-height 1. Insert 18: Standard BST insertion places 18 as the right child of 10. It is colored red. No violation occurs because its parent (10) is black. The tree remains valid.

Insert 7: 7 is less than 10, so it becomes the left child of 10, colored red. Again, its parent is black, so no fix-up is needed. At this point the tree is balanced: root 10 (B) with children 7 (R) and 18 (R), black-height 1 on all paths.

Insert 15: 15 is greater than 10 and less than 18, so it becomes the left child of 18, colored red. Now we have a violation: 15's parent (18) is red, and 18's parent (10) is black, but 15's uncle (7) is red. This is Case 1. We recolor 18 and 7 to black, and recolor 10 to red, then recolor the root back to black (the final step of fix-up always ensures root is black). After recoloring, 10 remains black, 7 and 18 become black, and 15 remains red. Black-height increases to 2.

Insert 16: 16 is greater than 10, less than 18, greater than 15, so it becomes the right child of 15, colored red. Now 16's parent (15) is red, its uncle (NIL) is black, and the configuration is a triangle? Let's trace: grandparent is 18 (black), parent is 15 (red, left child of 18), new node 16 is right child of 15. This is a left-right triangle, Case 2. We left-rotate on 15, making 16 the parent of 15. The structure becomes 18 with left child 16, and 16 with left child 15. Now we are in Case 3 (line): 16 is left child of 18? Actually after rotation, z is now 15 (the old parent), which is left child of 16, which is left child of 18 - a line. We recolor 16 to black and 18 to red, then right-rotate on 18. The final tree has root 10 (B), left child 7 (B), right child 16 (B), with children 15 (R) and 18 (R) under 16. All paths have black-height 2, and no red node has a red child.

This example shows how the tree remains approximately balanced with height 3 instead of degrading to height 5 as a naive BST would. The total cost was one recoloring propagation and two rotations, all O(log n).

5. Complexity Analysis

The height guarantee is the foundation of red-black tree performance. A proof sketch shows that a subtree rooted at node x contains at least 2^{bh(x)} - 1 internal nodes, where bh(x) is the black-height of x. Since at least half the nodes on any root-to-leaf path are black (no two reds adjacent), h <= 2 * bh(root). Combining these yields n >= 2^{h/2} - 1, so h <= 2 log2(n+1). This is O(log n) worst-case height, unlike a BST which can be O(n).

Search operation follows a single path from root to leaf, performing one comparison per level, so it is O(h) = O(log n) in all cases. There is no best-case improvement beyond O(log n) for a successful search because the tree is never perfectly shallow, but an unsuccessful search that terminates early at a shallow leaf can be slightly faster in practice.

Insertion requires O(log n) to find the insertion point via BST search, plus O(log n) for the fix-up loop. Although the loop can iterate up to O(log n) times (Case 1 propagates upward), each iteration moves up two levels, and rotations are at most 2 per insertion. Therefore worst-case insertion is O(log n) with low constant factors. Deletion is similar: O(log n) to find the node and O(log n) for fix-up, with at most 3 rotations.

Space complexity is O(n) for n keys, with each node storing key, color (1 bit, but typically 1 byte), left, right, and parent pointers. This is 4 pointers + 1 color per node plus the sentinel NIL. Compared to AVL trees which store a balance factor (-1,0,1), red-black trees have essentially identical memory overhead. The recursion stack for iterative implementations is O(log n), while recursive traversals also use O(log n) stack space, or O(n) in the worst case if the implementation is not tail-optimized.

6. Variations and Optimizations

The classic red-black tree has several important variants that optimize for specific workloads. The most famous is the Left-Leaning Red-Black Tree (LLRB) introduced by Robert Sedgewick in 2008. LLRB enforces the additional invariant that every red node must be a left child, which eliminates one symmetric case and simplifies implementation to under 100 lines. LLRBs are isomorphic to 2-3 trees and are often used for teaching and in functional languages, though they may perform slightly more rotations than the standard variant.

Another optimization is to augment the tree with additional data. An Order-Statistic Tree augments each node with a size field (number of nodes in its subtree), enabling O(log n) select (find k-th smallest) and rank (find rank of a key) operations. This is used in database indexes for pagination and percentile queries. An Interval Tree augments with max endpoint to support O(log n + k) overlapping interval queries, critical for calendar scheduling and genomic interval searches.

For concurrent environments, lock-free and fine-grained locking red-black trees have been developed. Techniques include using copy-on-write, optimistic concurrency with version counters, or implementing the tree as a persistent (immutable) data structure where each update returns a new root sharing unchanged subtrees. Clojure's sorted map and many functional implementations use this persistent approach, achieving O(log n) updates without locks.

Memory optimization is also common. Instead of storing a boolean color, some implementations store the color in the lowest bit of a pointer (pointer tagging) since pointers are aligned. Others eliminate parent pointers by using a stack during traversal, trading O(log n) time for reduced node size. For cache performance, B+ tree variants or cache-oblivious red-black trees that cluster nodes in memory can reduce cache misses by 30-40% on large datasets.

When to Prefer a Variant

Choose LLRB when code simplicity and maintainability outweigh raw throughput and you need a quick, correct implementation. Choose an augmented red-black tree when you need order statistics or interval queries on top of ordered mapping. For high-concurrency read-heavy workloads, consider a persistent or copy-on-write variant to avoid reader-writer locks entirely.

7. Real-World Applications

Red-black trees are ubiquitous in systems software because they provide guaranteed O(log n) worst-case performance with good average-case constants and in-order traversal. The Linux kernel uses a red-black tree for the Completely Fair Scheduler (CFS) to track runnable processes ordered by virtual runtime. The scheduler needs to repeatedly find the process with the smallest vruntime (minimum), insert newly woken processes, and delete the running process, all in O(log n) with deterministic latency, which a hash table cannot provide due to lack of ordering.

In programming language runtimes, Java's TreeMap and TreeSet, C++ std::map and std::set (in most implementations), and C# SortedDictionary are all red-black trees. These are used for ordered dictionaries, range queries, and when deterministic iteration order matters. For example, a web server might use a TreeMap to maintain active sessions ordered by expiration time, allowing efficient cleanup of expired sessions via range deletion.

Databases and file systems rely heavily on balanced trees. While many databases use B-trees for disk-based storage (due to better block locality), their in-memory indexes, lock managers, and query optimizers often use red-black trees. The ext3 and XFS file systems use red-black trees to manage extents and directory entries in memory. Network routers use red-black trees to store IP routing tables for longest-prefix match when the table fits in memory and requires frequent updates.

Other notable uses include memory allocators (e.g., jemalloc uses red-black trees to manage free blocks by size and address), real-time systems where worst-case guarantees are critical, and computational geometry algorithms like sweep-line for segment intersection. Any application requiring an ordered set or map with predictable performance and low memory overhead is a candidate.

8. Comparison with Alternatives

Choosing a balanced tree or alternative dictionary structure depends on workload characteristics: read vs. write ratio, need for ordering, persistence requirements, and memory constraints. A red-black tree offers a balanced compromise, but it is not always optimal.

AVL trees are more strictly balanced, maintaining height at most 1.44 log2 n versus 2 log2 n for red-black trees. This makes AVL searches about 10-15% faster due to shallower height, but insertions and deletions require more rotations (up to O(log n) rotations vs. O(1) for red-black). Therefore AVL is preferable for read-heavy, rarely updated ordered maps, such as compiler symbol tables that are built once and queried many times.

B-trees and B+ trees generalize BSTs to have many keys per node, optimizing for disk and SSD access where block reads dominate. They are the standard for database indexes and file systems because they reduce I/O operations by an order of magnitude. However, for purely in-memory data, their larger node size and more complex split logic make them slower than red-black trees.

Hash tables provide O(1) average search, insert, and delete, outperforming any tree for unordered dictionaries. They are the default choice when ordering is not needed. However, they have O(n) worst-case performance, high memory overhead for load factor management, and cannot support range queries, predecessor/successor, or sorted iteration efficiently. Skip lists offer similar O(log n) guarantees with simpler probabilistic balancing and good concurrency, but with higher memory overhead and less cache locality.

* Skip list worst-case O(n) is extremely unlikely with proper random level generation; expected is O(log n).

9. Common Mistakes and Best Practices

Implementing red-black trees is notoriously error-prone, with many subtle bugs that pass simple tests but fail under specific insertion orders. The most common mistake is mishandling the NIL sentinel. Forgetting to set NIL's parent, or comparing a node to None instead of NIL, causes null pointer errors or incorrect black-height calculations. Always initialize NIL.left, NIL.right, and NIL.parent to NIL itself, and ensure every leaf points to NIL, not None.

Another frequent error is forgetting to recolor the root black after insertion fix-up. Case 1 can propagate a red color to the root, violating the root property. The final line `self.root.color = Color.BLACK` is not optional, even if it seems redundant. Similarly, during deletion, failing to handle the case where x is NIL (the sentinel) in fix-up leads to incorrect double-black resolution. The fix-up loop must correctly treat NIL as black.

Rotation bugs are also common: updating child pointers but forgetting parent pointers, or forgetting to update the root pointer when rotating the root. A robust practice is to write a helper `transplant` function and reuse it, and to unit-test rotations in isolation with small trees. Additionally, many implementations incorrectly handle duplicate keys. Decide upfront whether to allow duplicates (e.g., by storing a count or list) or to reject them, and ensure search and insert are consistent.

For best practices, always implement iterative insertion and deletion rather than recursive to avoid stack overflow on large trees. Use assertions to verify invariants after every operation during development: check BST ordering via inorder traversal, verify no red-red adjacency via DFS, and verify black-height uniformity by checking all root-to-leaf paths. Property-based testing with random insertion/deletion sequences compared against a sorted list or Python's `bisect` is highly effective at catching rare bugs.

Checklist for Production Code

• Use a single shared NIL sentinel, not None, for all leaves.
• Verify all five invariants with a `validate()` method after each mutation in debug builds.
• Handle duplicates explicitly and document the policy.
• Ensure parent pointers are updated in both rotations and transplants.
• Test edge cases: empty tree, single node, sorted insertion (1..n), reverse sorted, and random sequences with interleaved deletes.
• Prefer iterative over recursive for large n to avoid recursion limits.
• Document whether the tree is thread-safe; if not, require external locking.

10. Interview Questions

Red-black trees are a favorite in senior engineering interviews because they test understanding of balancing, invariants, and trade-offs beyond simple BSTs. Expect both conceptual and coding questions.

Q1: Why does a red-black tree guarantee O(log n) height? Prove the bound.

Answer: Show that a subtree with black-height bh has at least 2^bh - 1 internal nodes by induction. Since red nodes cannot be adjacent, h ≤ 2*bh. Combining gives n ≥ 2^{h/2} - 1, so h ≤ 2 log2(n+1). Be prepared to walk through the induction base case (bh=0) and inductive step, and explain why the red property implies at least half the nodes on any path are black. Interviewers often ask for the exact constant factor (2) and why AVL's is tighter.

Q2: Insert keys [41, 38, 31, 12, 19, 8] into an empty red-black tree. Show the tree after each insertion and the fix-up cases used.

Answer: This tests your ability to simulate fix-up. 41 (B root), 38 (R left of 41) no violation, 31 (R left of 38) triggers Case 3 (line, uncle black) → recolor 38 black, 41 red, right rotate 41. Now 38 is root (B). 12 (R left of 31) no violation? Actually parent 31 is red, uncle 41 is red → Case 1 recolor. Continue similarly. Practice drawing the tree and explicitly naming uncle colors and triangle/line configurations. Mention that you always insert red and fix double-red.

Q3: Compare red-black tree vs. hash table vs. AVL tree. When would you choose each?

Answer: Structure your answer by workload. Hash table for O(1) average unordered lookup when ordering not needed and worst-case O(n) is acceptable (e.g., caches, frequency counting). AVL for read-heavy ordered data where search speed is paramount and writes are rare. Red-black for general-purpose ordered map with frequent writes, where fewer rotations matter (e.g., language stdlib maps, scheduler). Mention B-tree for disk-based storage. Bonus points for mentioning memory overhead and concurrency.

Q4: How would you augment a red-black tree to support order statistics (k-th smallest) in O(log n)?

Answer: Add a `size` field to each node storing subtree size. Maintain it during rotations and insert/delete (update size on the path). To find k-th smallest, start at root: let left_size = root.left.size + 1 (including NIL size 0). If k == left_size, return root; if k < left_size, recurse left; else recurse right with k - left_size. Rank is symmetric. Explain that augmentation does not affect O(log n) height and only adds O(1) overhead per rotation. This is how many databases implement pagination.

Q5: Implement deletion fix-up or explain the double-black concept.

Answer: Deleting a black node reduces black-height on one path by one, creating a double-black node that must be fixed. Explain the four deletion cases based on sibling color and sibling's children colors, and how rotations borrow black height from the sibling subtree. You may not need to code the full fix-up, but you should be able to explain why deleting a red node needs no fix-up, and why the fix-up terminates. Interviewers look for understanding that deletion is harder than insertion and requires handling the sibling's nephews.

To prepare, implement the full tree from scratch without referencing code, then validate it with a brute-force tester that inserts and deletes 10,000 random keys and compares inorder traversal to a sorted list while checking all five invariants after each operation.