# The Sorted Import That Made Search Crawl: Why Balance Matters

Keep a contact list fast however its names arrive: see why a sorted import turns a plain binary search tree into a line as slow as a list, why shuffling and rebuilding don't fix it, and which always-balanced sorted map your language gives you.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain why adding sorted data turns a plain binary search tree into a slow line
- Pick your language's sorted map, or what to use where there is none

## Key takeaways

- A binary search tree is only as fast as it is short: every operation walks one path, so its cost is the tree's height.
- Adding values in sorted order makes each one the right child of the last, so the tree becomes a line and search becomes O(n).
- Shuffling fails for keys that always grow, such as sign-up numbers, and rebuilding after every add costs O(n) each time.
- Self-balancing trees, such as AVL and red-black trees, rotate nodes after each change to keep the height near log n.
- C#'s SortedDictionary and Java's TreeMap are self-balancing trees; Python and JavaScript have no built-in sorted map.

**Before this:** *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees* finds a name in about log n checks, but only while the tree stays short and bushy.

Here is a bug that passes every test and then shows up in real use. You build the sales team's contact list on a binary search tree. It's fast in testing, where you typed contacts in any old order. Then a user imports 5,000 contacts from a file that's already sorted A to Z, and every search crawls. Nothing in the code changed; only the order the data arrived in. This lesson finds out why, tries the obvious fixes, and ends with the ready-made, always-balanced tree your language already has.

## The same names, a different shape

A binary search tree's shape depends on the order the values arrive. Add the contacts Maya, Diego, Tom, Ana, Kai, Rosa, Zoe, and you get the bushy tree from the last lesson: height 2. Add the same seven names in A to Z order, Ana, Diego, Kai, Maya, Rosa, Tom, Zoe, and something sad happens:

- Ana is the root.
- Diego is bigger than Ana, so he goes right.
- Kai is bigger than Ana, and bigger than Diego, so he goes right of Diego.
- Every name after that is bigger than all the ones before it, so it goes right, right, right, to the end.

![The same seven contacts added in two different orders. On the left, added A to Z, they make a line leaning to the right: Ana, then Diego, then Kai, then Maya, Rosa, Tom and Zoe, each the right child of the one before, height 6. On the right, added middle first, they make a balanced tree: Maya at the root, Diego and Tom under her, and Ana, Kai, Rosa and Zoe at the bottom, height 2](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/23fc206180a54d02881a6c1bda5f7afc.webp)

It's still a binary search tree: the rule holds at every node. But it's also a linked list wearing a tree costume. Finding Zoe means checking all seven names, one by one. Search is O(n) again.

## Measuring it

The program below adds the same 255 contacts two ways and measures each tree. To keep the numbers easy to check, the contacts are numbered 1 to 255 in A to Z order. The first tree gets them in order. The second gets them **middle first**: 128, then the middle of each half (64 and 192), then the middle of each quarter, and so on, the order binary search would ask about them in. For each tree it prints the height and how many checks it takes to find contact 255, the last one.

```csharp
Tree inOrder = new Tree();
for (int number = 1; number <= 255; number++)
{
    inOrder.Add(number);
}
Tree middleFirst = new Tree();
AddMiddleFirst(middleFirst, 1, 255);

Console.WriteLine("Added in order: height " + inOrder.Height() + ", " + inOrder.ChecksToFind(255) + " checks to find 255");
Console.WriteLine("Added middle first: height " + middleFirst.Height() + ", " + middleFirst.ChecksToFind(255) + " checks to find 255");

void AddMiddleFirst(Tree tree, int low, int high)
{
    if (low > high)
    {
        return;
    }
    int middle = (low + high) / 2;
    tree.Add(middle);
    AddMiddleFirst(tree, low, middle - 1);
    AddMiddleFirst(tree, middle + 1, high);
}

class Node
{
    public int Value { get; }
    public Node? Left { get; set; }
    public Node? Right { get; set; }

    public Node(int value)
    {
        Value = value;
    }
}

class Tree
{
    private Node? root;

    public void Add(int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return;
        }
        Node current = root;
        while (true)
        {
            if (value < current.Value)
            {
                if (current.Left == null)
                {
                    current.Left = new Node(value);
                    return;
                }
                current = current.Left;
            }
            else
            {
                if (current.Right == null)
                {
                    current.Right = new Node(value);
                    return;
                }
                current = current.Right;
            }
        }
    }

    public int ChecksToFind(int value)
    {
        int checks = 0;
        Node? current = root;
        while (current != null)
        {
            checks++;
            if (value == current.Value)
            {
                break;
            }
            current = value < current.Value ? current.Left : current.Right;
        }
        return checks;
    }

    public int Height()
    {
        return HeightOf(root);
    }

    private int HeightOf(Node? node)
    {
        if (node == null)
        {
            return -1;
        }
        return 1 + Math.Max(HeightOf(node.Left), HeightOf(node.Right));
    }
}
```

```text
Added in order: height 254, 255 checks to find 255
Added middle first: height 7, 8 checks to find 255
```

```java
class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
    }
}

class Tree {
    private Node root;

    void add(int value) {
        if (root == null) {
            root = new Node(value);
            return;
        }
        Node current = root;
        while (true) {
            if (value < current.value) {
                if (current.left == null) {
                    current.left = new Node(value);
                    return;
                }
                current = current.left;
            } else {
                if (current.right == null) {
                    current.right = new Node(value);
                    return;
                }
                current = current.right;
            }
        }
    }

    int checksToFind(int value) {
        int checks = 0;
        Node current = root;
        while (current != null) {
            checks++;
            if (value == current.value) {
                break;
            }
            current = value < current.value ? current.left : current.right;
        }
        return checks;
    }

    int height() {
        return heightOf(root);
    }

    private int heightOf(Node node) {
        if (node == null) {
            return -1;
        }
        return 1 + Math.max(heightOf(node.left), heightOf(node.right));
    }
}

void addMiddleFirst(Tree tree, int low, int high) {
    if (low > high) {
        return;
    }
    int middle = (low + high) / 2;
    tree.add(middle);
    addMiddleFirst(tree, low, middle - 1);
    addMiddleFirst(tree, middle + 1, high);
}

void main() {
    Tree inOrder = new Tree();
    for (int number = 1; number <= 255; number++) {
        inOrder.add(number);
    }
    Tree middleFirst = new Tree();
    addMiddleFirst(middleFirst, 1, 255);

    IO.println("Added in order: height " + inOrder.height() + ", " + inOrder.checksToFind(255) + " checks to find 255");
    IO.println("Added middle first: height " + middleFirst.height() + ", " + middleFirst.checksToFind(255) + " checks to find 255");
}
```

```text
Added in order: height 254, 255 checks to find 255
Added middle first: height 7, 8 checks to find 255
```

```python
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None

    def add(self, value):
        if self.root is None:
            self.root = Node(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = Node(value)
                    return
                current = current.left
            else:
                if current.right is None:
                    current.right = Node(value)
                    return
                current = current.right

    def checks_to_find(self, value):
        checks = 0
        current = self.root
        while current is not None:
            checks += 1
            if value == current.value:
                break
            current = current.left if value < current.value else current.right
        return checks

    def height(self):
        return self._height_of(self.root)

    def _height_of(self, node):
        if node is None:
            return -1
        return 1 + max(self._height_of(node.left), self._height_of(node.right))


def add_middle_first(tree, low, high):
    if low > high:
        return
    middle = (low + high) // 2
    tree.add(middle)
    add_middle_first(tree, low, middle - 1)
    add_middle_first(tree, middle + 1, high)


in_order = Tree()
for number in range(1, 256):
    in_order.add(number)
middle_first = Tree()
add_middle_first(middle_first, 1, 255)

print(f"Added in order: height {in_order.height()}, {in_order.checks_to_find(255)} checks to find 255")
print(f"Added middle first: height {middle_first.height()}, {middle_first.checks_to_find(255)} checks to find 255")
```

```text
Added in order: height 254, 255 checks to find 255
Added middle first: height 7, 8 checks to find 255
```

```javascript
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  add(value) {
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) {
          current.left = new Node(value);
          return;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = new Node(value);
          return;
        }
        current = current.right;
      }
    }
  }

  checksToFind(value) {
    let checks = 0;
    let current = this.root;
    while (current !== null) {
      checks++;
      if (value === current.value) {
        break;
      }
      current = value < current.value ? current.left : current.right;
    }
    return checks;
  }

  height() {
    return this.#heightOf(this.root);
  }

  #heightOf(node) {
    if (node === null) {
      return -1;
    }
    return 1 + Math.max(this.#heightOf(node.left), this.#heightOf(node.right));
  }
}

function addMiddleFirst(tree, low, high) {
  if (low > high) {
    return;
  }
  const middle = Math.floor((low + high) / 2);
  tree.add(middle);
  addMiddleFirst(tree, low, middle - 1);
  addMiddleFirst(tree, middle + 1, high);
}

const inOrder = new Tree();
for (let number = 1; number <= 255; number++) {
  inOrder.add(number);
}
const middleFirst = new Tree();
addMiddleFirst(middleFirst, 1, 255);

console.log(`Added in order: height ${inOrder.height()}, ${inOrder.checksToFind(255)} checks to find 255`);
console.log(`Added middle first: height ${middleFirst.height()}, ${middleFirst.checksToFind(255)} checks to find 255`);
```

```text
Added in order: height 254, 255 checks to find 255
Added middle first: height 7, 8 checks to find 255
```

```typescript
class TreeNode {
  value: number;
  left: TreeNode | null = null;
  right: TreeNode | null = null;

  constructor(value: number) {
    this.value = value;
  }
}

class Tree {
  private root: TreeNode | null = null;

  add(value: number): void {
    if (this.root === null) {
      this.root = new TreeNode(value);
      return;
    }
    let current = this.root;
    while (true) {
      if (value < current.value) {
        if (current.left === null) {
          current.left = new TreeNode(value);
          return;
        }
        current = current.left;
      } else {
        if (current.right === null) {
          current.right = new TreeNode(value);
          return;
        }
        current = current.right;
      }
    }
  }

  checksToFind(value: number): number {
    let checks = 0;
    let current = this.root;
    while (current !== null) {
      checks++;
      if (value === current.value) {
        break;
      }
      current = value < current.value ? current.left : current.right;
    }
    return checks;
  }

  height(): number {
    return this.heightOf(this.root);
  }

  private heightOf(node: TreeNode | null): number {
    if (node === null) {
      return -1;
    }
    return 1 + Math.max(this.heightOf(node.left), this.heightOf(node.right));
  }
}

function addMiddleFirst(tree: Tree, low: number, high: number): void {
  if (low > high) {
    return;
  }
  const middle = Math.floor((low + high) / 2);
  tree.add(middle);
  addMiddleFirst(tree, low, middle - 1);
  addMiddleFirst(tree, middle + 1, high);
}

const inOrder = new Tree();
for (let number = 1; number <= 255; number++) {
  inOrder.add(number);
}
const middleFirst = new Tree();
addMiddleFirst(middleFirst, 1, 255);

console.log(`Added in order: height ${inOrder.height()}, ${inOrder.checksToFind(255)} checks to find 255`);
console.log(`Added middle first: height ${middleFirst.height()}, ${middleFirst.checksToFind(255)} checks to find 255`);
```

```text
Added in order: height 254, 255 checks to find 255
Added middle first: height 7, 8 checks to find 255
```

The same 255 contacts, the same code: 255 checks one way, 8 the other. An empty spot has height -1 here, so that a single node comes out at 0, matching *Who Works Under Whom? Trees*. The TypeScript version calls its node class `TreeNode`, because TypeScript already has a built-in type named `Node` for web pages.

**Try it.** Change every 255 in the program to 511 (in Python, `range(1, 256)` becomes `range(1, 512)`) and run it again. The line now needs 511 checks to find the last contact; the balanced tree needs only 9. Twice the contacts: twice the checks for the line, one more for the balanced tree.

## What would you try?

You can't make users add their contacts middle first. So how do you keep the tree short?

**Shuffle the names before adding them.** For a one-off import, add the 5,000 contacts in random order and the tree comes out bushy enough: in 20 shuffled runs it was 24 to 31 levels tall, against 12 for a perfect tree and 4,999 for the line. But it fails when the keys arrive one at a time, already in order: customer numbers handed out 1, 2, 3 as people sign up, or orders stamped with the time. You can't shuffle what hasn't arrived yet, and each new key is the biggest so far, so it goes right, right, right.

**Rebuild the tree after every add.** Walk it in order, which gives the names sorted, and build it again middle first, as the program above does. Every rebuild gives a perfect tree, but every rebuild also touches every contact: O(n) for one add, the sorted array's problem all over again. Adding 5,000 contacts one at a time, with a walk and a rebuild after each, is about 25 million steps, where the adds alone take about 60,000.

**Rebuild now and then.** Rebuild after every 500 adds, say. That's cheaper, but between rebuilds the tree leans again, and with always-growing keys, the newest 500 hang off the bottom in a line every time.

| What we tried | Cost per add | Where it breaks |
|---|---|---|
| Shuffle first | O(log n) on average | keys that always grow arrive in order |
| Rebuild after every add | O(n): about 25 million steps for 5,000 adds | every add pays for the whole tree |
| Rebuild now and then | cheap on average | the tree leans between rebuilds |

## The question that leads to it

Rebuilding fixed the whole tree when only one small part of it leaned: the bottom of the right side. **Can we fix only the piece that starts to lean, right when it leans?** If each add checked the few nodes on its own path and straightened the first one that leaned too far, the fix would cost about as much as the add: O(log n).

## Self-balancing trees

That idea was so useful that it got a name: a **self-balancing tree**, a binary search tree that checks its own shape after every add and remove, along the path it changed, and fixes it when one side gets too tall.

The fix is a **rotation**: a small swap of a parent and a child that makes one side shorter and the other taller, without breaking the left-smaller, right-bigger rule. Picture three contacts in a line, Ana, then Diego on her right, then Kai on his. Rotate, and Diego becomes the parent, with Ana on his left and Kai on his right. Same three names, still in order, and one level shorter.

![A rotation in two frames. Before: three contacts in a line leaning right, Ana at the top, Diego as her right child and Kai as his right child, height 2. After: Diego at the top with Ana as his left child and Kai as his right child, height 1. The names are in the same A to Z order in both frames](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/0fe9b11a935e4dbd958984aab62ab387.webp)

The two you'll hear about most:

- **AVL trees** keep the two sides of every node within one level of each other. Very short, so searching is as fast as it gets.
- **Red-black trees** allow a little more lean, so they rotate less often when data changes a lot. They're the ones inside most languages' libraries.

Both keep the height near log n, however the data arrives, shuffled, sorted or one sign-up at a time, so search, add and remove stay O(log n) in the worst case, not only on lucky days. You don't need to write one: the rotation rules are fiddly, and every serious library already has one.

## The sorted map in your language

A **sorted map** is a dictionary that keeps its keys in order: look up by key like any dictionary, and also walk the keys A to Z. It's the self-balancing tree you'll use in real code.

```csharp
SortedDictionary<string, string> phones = new SortedDictionary<string, string>(StringComparer.Ordinal);
phones["Zoe"] = "555-0198";
phones["Ana"] = "555-0142";
phones["Maya"] = "555-0110";
phones["Kai"] = "555-0177";

foreach (KeyValuePair<string, string> contact in phones)
{
    Console.WriteLine(contact.Key + ": " + contact.Value);
}
```

```text
Ana: 555-0142
Kai: 555-0177
Maya: 555-0110
Zoe: 555-0198
```

```java
void main() {
    TreeMap<String, String> phones = new TreeMap<>();
    phones.put("Zoe", "555-0198");
    phones.put("Ana", "555-0142");
    phones.put("Maya", "555-0110");
    phones.put("Kai", "555-0177");

    for (Map.Entry<String, String> contact : phones.entrySet()) {
        IO.println(contact.getKey() + ": " + contact.getValue());
    }
}
```

```text
Ana: 555-0142
Kai: 555-0177
Maya: 555-0110
Zoe: 555-0198
```

```python
phones = {}
phones["Zoe"] = "555-0198"
phones["Ana"] = "555-0142"
phones["Maya"] = "555-0110"
phones["Kai"] = "555-0177"

for name in sorted(phones):
    print(f"{name}: {phones[name]}")
```

```text
Ana: 555-0142
Kai: 555-0177
Maya: 555-0110
Zoe: 555-0198
```

```javascript
const phones = new Map();
phones.set("Zoe", "555-0198");
phones.set("Ana", "555-0142");
phones.set("Maya", "555-0110");
phones.set("Kai", "555-0177");

for (const name of [...phones.keys()].sort()) {
  console.log(`${name}: ${phones.get(name)}`);
}
```

```text
Ana: 555-0142
Kai: 555-0177
Maya: 555-0110
Zoe: 555-0198
```

```typescript
const phones = new Map<string, string>();
phones.set("Zoe", "555-0198");
phones.set("Ana", "555-0142");
phones.set("Maya", "555-0110");
phones.set("Kai", "555-0177");

for (const name of [...phones.keys()].sort()) {
  console.log(`${name}: ${phones.get(name)}`);
}
```

```text
Ana: 555-0142
Kai: 555-0177
Maya: 555-0110
Zoe: 555-0198
```

Only two of the five languages have a sorted map built in. C#'s `SortedDictionary<TKey, TValue>` and Java's `TreeMap<K, V>` are red-black trees: they keep the keys in order all the time. Python's `dict` and JavaScript's `Map` are hash tables (Module 5), so they keep keys in the order they were **added**, not sorted; the Python, JavaScript and TypeScript versions sort the keys each time they need them in order, which is O(n log n) per listing. When a Python program needs order all the time, the usual choice is the `sortedcontainers` package from PyPI, installed with `pip`; in JavaScript and TypeScript it's a package from npm, or the binary search tree you built in the last lesson.

## The cost card: plain and self-balancing

| Operation | Plain binary search tree, worst case | Self-balancing tree or sorted map | Why, in everyday terms |
|---|---|---|---|
| Search, add, remove | O(n) | O(log n) | A line makes you check every name; a balanced tree halves what's left each step |
| List everything in order | O(n) | O(n) | Everyone is visited once either way |
| Smallest or largest key | O(n) | O(log n) | Walk all the way left, or all the way right |

A sorted map costs more per operation than a hash table's O(1) dictionary. Pick it when you need the keys in order, such as listing contacts A to Z or finding everyone between two dates; otherwise the plain dictionary is faster.

## Check yourself

2 questions to try on the lesson page.

## So what

A binary search tree is only as fast as it is short, and sorted data makes it as tall as possible. When you need data kept in order, reach for your language's sorted map, which balances itself, and when you build your own tree, remember that the order data arrives in decides its shape.

## Key terms

- [Balanced Tree](https://www.ask-codey.com/glossary/balanced-tree)
- [Self-Balancing Tree](https://www.ask-codey.com/glossary/self-balancing-tree)
- [Sorted Map](https://www.ask-codey.com/glossary/sorted-map)
- [Tree Height](https://www.ask-codey.com/glossary/tree-height)

## Cheat sheets

- [The Sorted Import That Made Search Crawl: Why Balance Matters](https://www.ask-codey.com/cheat-sheets/ds-tree-balance-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-tree-balance
