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

By

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, also linked from the Exercise box beside the lesson. Clone it into your course folder. In a terminal, in that folder:

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):

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.

<details> <summary>Stuck?</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.

</details>

When you're done

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

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?

<details> <summary>Why Should I Choose This?</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.

</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".

<details> <summary>Some answers</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.

</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:

    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

Related