# Exercise: The Contact List Tree

The sales team's 100,000 contacts need a find on every keystroke, adds all day, A to Z on demand, and removals: build the contact list, name each operation's growth rate, and pass a busy-day test that only a fast choice can.

Journeyman · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

Here's the ticket from the sales team's app lead:

> Our shared contact list will hold 100,000 people, and it has four jobs:
>
> 1. **Find as you type.** Every keystroke in the search box looks a name up, so a find has to be quick however many contacts there are.
> 2. **Add all day.** New contacts arrive from forms and imports. Adding a name we already have updates their phone number instead.
> 3. **A to Z on demand.** The contacts screen lists everyone in alphabetical order whenever it opens, without sorting them first.
> 4. **Remove** a contact who has left, and say whether they were there.
>
> **Too slow:** adding 100,000 contacts and then finding every one of them takes more than 2 seconds.

You followed a search down the contact tree and watched three contacts being removed in *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees*. Now you build the whole contact list, and the tests end with that busy day.

## Before you start

You need one language set up, as in *Setup: VS Code and Your Language*. The exercise is written in all five of the course's languages; pick the one you use.

## Get the exercise code

Open this lesson's GitHub repository, [github.com/ask-codey/exercise-ds-contact-tree](https://github.com/ask-codey/exercise-ds-contact-tree), also linked from the **Exercise** box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

```bash
git clone https://github.com/ask-codey/exercise-ds-contact-tree.git
```

Git makes a folder, `exercise-ds-contact-tree`, with the exercise code inside.

The repository has a folder for each language: `csharp`, `java`, `python`, `javascript` and `typescript`. Each folder holds:

- **your code:** the `ContactTree` class, with its methods to finish (the repository's `README.md` names the file for each language);
- **the `Contact` class:** one node of the tree, with a name, a phone number, and `left` and `right` children. You don't need to change it;
- **the tests** that check your methods. You don't need to change them either;
- **a demo program** that tries your contact list on seven contacts.

In VS Code, choose **File > Open Folder** and open **your language's folder**, not the whole repository.

## What to do

The class already has a `root`, empty at first, and a count of its contacts. Every method you finish is there, with its parameters, and does nothing or returns an empty answer for now. The comment above each one says what it should do, with examples, and ends with a **Growth rate:** line. Here is `find` in Python, as the starter has it (the other languages say the same in their own syntax):

```python
def find(self, name):
    """
    Find a contact's phone number by name, or None if there's no
    contact with that name.

    find("Kai") -> "555-0177"
    find("Lena") -> None

    Growth rate: (write it here)
    """
    return None
```

1. **Add a contact.** Finish `add` (`Add` in C#). Walk down from the root, left for a name earlier in the alphabet and right for a later one, and hang the new contact where the walk runs out. If the name is already there, update its phone number instead, and don't count it twice.
2. **Find a number.** Finish `find`: the same walk, stopping at the name, or giving nothing (`null`, or `None` in Python) when the walk runs out.
3. **List everyone A to Z.** Finish `namesInOrder` with an in-order walk.
4. **Remove a contact.** Finish `remove`, in all three cases from the lesson. It answers `true` when the contact was there and is now gone, and `false` when there was no such contact.
5. **Name the growth rates.** On each method's **Growth rate:** line, write its Big-O and a few words on why. For the tree's methods, say what happens when it's balanced and when it has become a line.

## Check your work

Each language has its own command, run in the terminal in your language's folder (**Terminal > New Terminal** in VS Code). The repository's `README.md` has the full list, including the one-time setup for Python (a virtual environment and pytest) and TypeScript (`npm install`).

| Language | Run the tests | Run the demo |
|---|---|---|
| C# | `dotnet test` | `dotnet run --project ContactTree` |
| Java | `./mvnw test` (`.\mvnw test` in PowerShell) | `java src/main/java/Demo.java` |
| Python | `python -m pytest` | `python demo.py` |
| JavaScript | `npm test` | `node demo.js` |
| TypeScript | `npm test` | `node demo.ts` |

At first all 10 tests fail. That's expected: each method you finish turns its tests green. A failing test's message starts with **Not yet:** and says what it expected, for example *Not yet: Diego has two children, so Kai, the next name in order, takes his place.* Near the end, one test adds 1,000 contacts out of order and removes half of them, so it passes only when every case works. The last is the busy day: 100,000 contacts added and found in under 2 seconds.

&lt;details>
&lt;summary>Stuck?&lt;/summary>

- **Where to look:** the ticket asks for what *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees* builds, a **binary search tree**: earlier names to the left, later ones to the right, so a find walks one path.
- **Names are compared the way a dictionary orders words,** character by character, so capital letters count: `string.CompareOrdinal` in C#, `compareTo` in Java, and `<` in Python, JavaScript and TypeScript.
- **Keep the count honest.** Add one when `add` makes a new contact (not when it updates a phone number), and take one away when `remove` takes a contact out.
- **For `remove`, write a helper** that takes a node and a name, and returns what should stand in that node's place afterward. Go left or right until you reach the name; then for a leaf return nothing, for one child return that child, and for two children copy the next name in order (right once, then left as far as you can) into this node and remove that name from the right side.
- **Check that the name is there before you remove it,** with your own `find`, so a missing name changes nothing.
- **Stuck on a growth rate?** Every method but the listing and the count walks one path from the root, so its cost is the tree's height: about log n when it's balanced, as in *The Sorted Import That Made Search Crawl: Why Balance Matters*, and n when the names arrived in order.

&lt;/details>

## When you're done

Every test is green, and the demo prints the same lines in every language:

```text
Contacts A to Z: Ana, Diego, Kai, Maya, Rosa, Tom, Zoe
Kai's number: 555-0177
Lena's number: not found
Removed Diego: yes
Contacts A to Z: Ana, Kai, Maya, Rosa, Tom, Zoe
Contacts: 6
```

Now imagine your user imports 10,000 contacts from a file that's already sorted A to Z. What shape does your tree end up, and how many checks does finding the last contact take? What would you use instead in real code?

&lt;details>
&lt;summary>Why Should I Choose This?&lt;/summary>

The busy day is 100,000 contacts added, then every one of them found.

- **An unsorted list, checked one by one:** each find reads about 50,000 names, and each add reads them all to check for a repeat: about 10 billion name checks, 89 seconds in C# and about four and a half minutes in Python.
- **A sorted array:** a find takes about 17 looks, but every new contact slides the names after it along, O(n). Computers slide memory in big blocks, so 100,000 can still pass, but ten times the contacts is a hundred times the sliding.
- **A dictionary:** finds and adds in O(1) on average, faster than the tree, but every A to Z screen sorts all 100,000 first, O(n log n).
- **Your tree:** a find or an add walks one path, at most 31 steps for the busy day's names, nothing slides, and A to Z is an in-order walk with no sort. It passes the busy day in well under a second.
- **What it gives up:** the order names arrive in decides its shape, which is why real code reaches for `SortedDictionary` or `TreeMap`, trees that balance themselves.

&lt;/details>

## Where else does this shape show up?

You've built "kept in order, quick to search, quick to change". Before you open the answers, think of three other places, on a screen or in daily life, where a list has to stay sorted while things are added to it all the time, and someone asks for "everything between this and that".

&lt;details>
&lt;summary>Some answers&lt;/summary>

- **A calendar** keeps events in time order as you add them, and shows everything between Monday and Friday.
- **A game's leaderboard** keeps scores in order as games finish, and shows the ten scores around yours.
- **A shop's price filter** shows every product between $20 and $50 while new products arrive.
- **A database index** keeps a column's values sorted for "every order from March": the B-tree from *One Row in a Billion: B-Trees and Database Indexes*.
- **A dictionary app** finds a word and shows the words just before and after it.

&lt;/details>

## Submit your exercise

The exercise is how you finish this lesson. When your work is done, put it on GitHub in a repo of your own, then submit that repo's address here.

1. On GitHub, click **+**, then **New repository**. Name it (for example `exercise-ds-contact-tree`), choose **Public**, and click **Create repository**. Leave out the README: your folder already has one.
2. In a terminal in your exercise folder (Git Bash on Windows), send your work to your new repo. Point your copy at your own repo, then commit and push:

   ```bash
   git remote set-url origin https://github.com/your-name/exercise-ds-contact-tree.git
   git add .
   git commit -m "My solution"
   git push -u origin main
   ```

3. Paste your repo's address, such as `https://github.com/your-name/exercise-ds-contact-tree`, into **Submit your exercise** on this page. The site checks that the repo is public and holds your commits, and then the lesson is complete.

Changed something after you submitted? Push it, and submit again: your latest submission is the one that counts.

## So what

You've built a sorted, searchable collection from nothing but nodes and two links each, including the removal that trips up most first attempts. When a sorted map in C# or Java finds a key in a few steps, you know what it's doing underneath.

## Key terms

- [Binary Search Tree](https://www.ask-codey.com/glossary/binary-search-tree)
- [In-Order Traversal](https://www.ask-codey.com/glossary/in-order-traversal)
- [Subtree](https://www.ask-codey.com/glossary/subtree)
- [Balanced Tree](https://www.ask-codey.com/glossary/balanced-tree)

## Related

- [A Contact List That's Fast to Search and Easy to Change: Binary Search Trees](https://www.ask-codey.com/lessons/ds-binary-search-trees)
- [The Sorted Import That Made Search Crawl: Why Balance Matters](https://www.ask-codey.com/lessons/ds-tree-balance)

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