Build a Contact Manager in Python

Build a Hash Map, Stack, and BST from scratch to power a CLI contact manager.

Introduction

30 Second Summary

Every time you search a contact on your phone, something decides how to find that name instantly among thousands of entries. Behind the scenes, data structures like hash maps and trees make that speed possible.

In this project, you will build a Contact Manager command-line app powered entirely by data structures you create from scratch. No built-in dictionaries or libraries allowed.

What You'll Build

A Contact Manager CLI backed by a Hash Map for instant lookups, a Stack for undo history, and a Binary Search Tree for sorted data and range queries.

By the end of this project, you'll have:

  • A working Hash Map with hashing, collision handling via chaining, and automatic resizing when the load factor exceeds 0.7.
  • A Stack that powers an undo system, letting you reverse any action you take in the contact manager.
  • A Binary Search Tree that keeps contacts sorted alphabetically and enables range queries to find contacts between any two letters.
  • Secret Mission: Add prefix search (autocomplete) so typing "da" finds "daniel", "dave", and "darren".

Are there any prerequisites?

This project assumes you're comfortable with intermediate Python. You should know how to work with classes, functions, lists, loops, and conditionals.

Before We Start

You're building a Contact Manager CLI from scratch. The real goal isn't just managing contacts. You'll build the engine underneath: a Hash Map for instant lookups, a Stack for undo history, and a Binary Search Tree for sorted data.

Before writing any code, you need Python ready and a project folder with the right files in place. Let's get that set up now.

In this step, get ready to:
  • Verify Python is installed.
  • Create the project folder and files.
  • Open the project in VS Code.
Verify Python is installed

This project runs on pure Python with no external libraries. You need Python 3.13 or higher to follow along.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Visual Studio Code and press Enter to open it.
  • Open the integrated terminal by pressing Ctrl+` (both macOS and Windows).
  • Check your Python version by running this command:

macOS

python3 --version

Windows

python --version

You should see a version number printed like Python 3.14.5 or Python 3.13.x.

✔️ I see Python 3.13 or higher

You're all set. Any version from 3.13 upwards works for this project since we use no version-specific features.

ⓧ I see an older version

You need Python 3.13 or higher. Download the latest version from the official Python downloads page:

  • Visit python.org/downloads and download Python 3.14.
  • Run the installer. On Windows, check the box that says Add Python to PATH before clicking Install Now.
  • Close and reopen VS Code, then open a new terminal and re-run the version check.

macOS users with an older system Python

macOS may ship with an older Python. After installing from python.org, use python3 --version to confirm the new version is available. If it still shows the old version, try python3.14 --version to call the new install directly.

ⓧ Command not found

Python isn't installed yet. Download and install it:

  • Visit python.org/downloads and download Python 3.14.
  • Run the installer. On Windows, check the box that says Add Python to PATH before clicking Install Now.
  • Close and reopen VS Code, then open a new terminal and re-run the version check.
Create your project structure

Your project needs four Python files, one for each data structure and one for the CLI that ties them together.

  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create the project folder and move into it by running these commands:
mkdir contact-manager
cd contact-manager
  • Create the four project files by running this command:

macOS

touch hash_map.py stack.py bst.py contact_manager.py

Windows

New-Item -ItemType File -Path "hash_map.py", "stack.py", "bst.py", "contact_manager.py"
  • Confirm the files exist by running:
ls

You should see hash_map.py, stack.py, bst.py, and contact_manager.py listed in the output.

Don't see all four files?

Make sure you ran the file creation command from inside the contact-manager folder. Run pwd (macOS) or cd (Windows) to check your current location.

If you're in the wrong folder, navigate back with cd ~/Desktop/contact-manager and try the file creation command again.

Help me create my project files

Open the project in VS Code

Now that the files exist, open the entire folder in VS Code so the editor knows about your project structure.

  • In VS Code, click File in the top menu bar.
  • Click Open Folder.
  • Navigate to your Desktop, select the contact-manager folder, and click Open.
  • Check the bottom-left of the VS Code status bar for the Python interpreter. It should show Python 3.14.x or Python 3.13.x.
  • If you see a different version or no interpreter, click the version number in the status bar and select Python 3.14 (or Python 3.13) from the dropdown.

You should now see your four files listed in the Explorer sidebar on the left.

Why four separate files?

Each file holds one data structure: hash_map.py for the Hash Map, stack.py for the Stack, and bst.py for the Binary Search Tree.

The fourth file, contact_manager.py, imports all three and wires them into the CLI application. Keeping each structure in its own file makes testing and debugging much easier.

Your environment is ready. Next up, you'll build the Hash Map from scratch and learn how Python's dict works under the hood.

Set Up Your Project

Before you build data structures from scratch, you need a clean workspace ready to go. This step confirms your Python version and project files are in place so you can focus entirely on code in the steps ahead.

You will verify Python is working, confirm your project structure, and check that VS Code is pointing at the right interpreter.

In this step, get ready to:
  • Confirm Python is installed and at the right version.
  • Verify your project folder and four Python files are in place.
  • Confirm the Python interpreter is selected in VS Code.
Verify your Python version

Your Contact Manager uses only core Python features (classes, lists, and f-strings), so any version from 3.13 onwards works perfectly. Let's confirm Python is ready.

  • Open the integrated terminal in VS Code by pressing Ctrl+` (macOS and Windows).
  • Check your Python version by running this command:
python --version

You should see output like Python 3.14.5 or Python 3.13.x. Either one works for this project.

Seeing command not found?

If your system doesn't recognise python, try python3 --version instead. On some systems the command is registered under python3.

If neither command works, download Python from python.org/downloads and re-run the installer.

help me fix my Python installation so I can run python --version

Verify your project structure

Your Contact Manager lives in four files, each responsible for one data structure or the app that ties them together.

  • In the terminal, confirm you are inside the contact-manager folder by running:
ls

You should see these four files listed in the output:

  • hash_map.py will hold your custom Hash Map.
  • stack.py will hold your Stack.
  • bst.py will hold your Binary Search Tree.
  • contact_manager.py will wire all three structures into a CLI app.

Why four separate files?

Each data structure lives in its own module so you can test it independently. When you build the Contact Manager in the final step, you will import from all three files. This mirrors how production codebases separate concerns into distinct modules.

Don't see all four files?

If any files are missing, create them by running:

touch hash_map.py stack.py bst.py contact_manager.py

Then run ls again to confirm all four appear.

help me create the missing project files in my contact-manager folder

Confirm your VS Code interpreter

VS Code needs to know which Python installation to use for linting and running your code.

  • Look at the bottom status bar in VS Code. You should see a Python version number (e.g. 3.14.5).
  • If you see multiple versions or the wrong one, click the version number in the status bar and select Python 3.14 (or Python 3.13 if that is what you have installed).

What is the Python interpreter?

The interpreter is the engine that reads and executes your Python code. If VS Code points at the wrong interpreter, you might get confusing errors about missing modules or syntax that does not match your installed version.

Your workspace is locked in and ready. Next up, you will build the first data structure: a Hash Map that turns any key into an instant lookup.

Build the Hash Map

Your project folder is ready with four empty files waiting to be filled. Now it's time to build the first data structure: a Hash Map that powers instant lookups.

A Hash Map turns any key (like a person's name) into a number, then uses that number as an index into an array. The result is O(1) average-time lookups, the same trick Python's built-in dict uses under the hood. You'll build one from scratch so you understand exactly how it works.

In this step, get ready to:
  • Build a hash function that converts keys into bucket indices.
  • Implement put, get, and remove with collision handling.
  • Add dynamic resizing so the map stays fast as it grows.
Create the HashMap class with the hash function

Every hash map starts with two pieces: an array of "buckets" to store data, and a hash function that decides which bucket each key goes into.

  • In VS Code, open hash_map.py from the Explorer sidebar.
  • Add the following code to create the HashMap class with its constructor and hash function:
class HashMap:
    def __init__(self, size=8):
        # Start with 8 buckets (each bucket is an empty list)
        self._size = size
        self._buckets = [[] for _ in range(self._size)]
        self._count = 0

    def _hash(self, key):
        # Convert any key into a valid bucket index
        return hash(key) % self._size

What does this code do?

The __init__ method creates 8 empty buckets (lists inside a list) and a counter to track how many items are stored.

The _hash method is the core idea. Python's built-in hash() turns any key into a large integer. The % self._size operation (modulo) squeezes that number down to a valid index between 0 and 7.

  • Save hash_map.py.

You won't see any output yet. The next chunk adds the methods that actually store and retrieve data.

Implement put, get, and remove

With the hash function ready, you need three operations: store a key-value pair, retrieve a value by key, and remove an entry. All three follow the same pattern: hash the key, find the bucket, then walk through the bucket's list.

  • In hash_map.py, add the put method below the _hash method:
    def put(self, key, value):
        # Resize if load factor exceeds 0.7
        if self._count / self._size >= 0.7:
            self._resize()

        index = self._hash(key)
        bucket = self._buckets[index]

        # Check if key already exists in this bucket
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        # Key not found, append new entry
        bucket.append((key, value))
        self._count += 1

What does this code do?

The put method first checks if the map is getting too full (load factor >= 0.7) and triggers a resize if needed. You'll write _resize in the next substep.

It then hashes the key to find the right bucket. If the key already exists in that bucket, it updates the value in place. If the key is new, it appends a tuple of (key, value) to the bucket's list. This list-per-bucket approach is called chaining and handles collisions (two keys landing in the same bucket).

  • Save hash_map.py.

You won't see output yet. The next method, get, lets you retrieve what you stored.

  • Add the get method below put:
    def get(self, key):
        index = self._hash(key)
        bucket = self._buckets[index]

        # Walk through the bucket looking for our key
        for k, v in bucket:
            if k == key:
                return v
        return None

What does this code do?

The get method hashes the key to find the right bucket, then loops through the entries in that bucket. If it finds a matching key, it returns the value. If the key isn't there, it returns None.

  • Save hash_map.py.
  • Verify that put and get work together by running this in your terminal:
python -c "from hash_map import HashMap; hm = HashMap(); hm.put('alice', '555-0001'); print(hm.get('alice'))"

You should see 555-0001 printed in the terminal.

Seeing an error instead?

  • If you see ModuleNotFoundError, make sure your terminal is in the contact-manager folder. Run cd ~/Desktop/contact-manager to get there.
  • If you see IndentationError, check that the method bodies are indented with 4 spaces under the def line and 8 spaces under the class.

Still stuck? Help me fix my HashMap put or get method

  • Add the remove method below get:
    def remove(self, key):
        index = self._hash(key)
        bucket = self._buckets[index]

        # Find and remove the matching entry
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._count -= 1
                return True
        return False

What does this code do?

The remove method follows the same hash-then-search pattern. When it finds the key, it pops the entry out of the bucket list and decrements the count. It returns True if the key was found and removed, or False if the key didn't exist.

  • Save hash_map.py.

The core operations are done. Next, you'll add resizing and helper methods to make the HashMap production-ready.

Add dynamic resizing and utility methods

Your HashMap currently has a fixed number of buckets. As more items pile in, each bucket's list grows longer, making lookups slower.

Dynamic resizing solves this by doubling the bucket count when the map gets too full. The threshold is called the load factor: the ratio of items to buckets. Once it exceeds 0.7, the map resizes.

  • Add the _resize method below remove:
    def _resize(self):
        # Save existing entries
        old_buckets = self._buckets
        # Double the number of buckets
        self._size *= 2
        self._buckets = [[] for _ in range(self._size)]
        self._count = 0

        # Rehash all existing entries into new buckets
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

Why rehash everything?

When the bucket count changes, every key's bucket index changes too (because hash(key) % new_size gives a different result than hash(key) % old_size). So _resize must re-insert every entry into the fresh, larger bucket array.

  • Save hash_map.py.

You won't see a change yet. The next chunk adds utility methods that make the HashMap easier to use.

  • Add the utility methods below _resize:
    def __contains__(self, key):
        return self.get(key) is not None

    def __len__(self):
        return self._count

    def keys(self):
        # Collect all keys from every bucket
        all_keys = []
        for bucket in self._buckets:
            for k, v in bucket:
                all_keys.append(k)
        return all_keys

What do these methods do?

  • __contains__ lets you write "alice" in hm to check if a key exists.
  • __len__ lets you write len(hm) to get the item count.
  • keys() returns a list of all stored keys by walking every bucket.
  • Save hash_map.py.

Now add a test block at the bottom of the file so you can verify everything works together.

  • Add this test code at the bottom of hash_map.py, outside the class (no indentation):
if __name__ == "__main__":
    hm = HashMap()
    hm.put("alice", {"phone": "555-0001"})
    hm.put("bob", {"phone": "555-0002"})
    hm.put("charlie", {"phone": "555-0003"})

    print(hm.get("alice"))
    print(hm.get("bob"))
    print("alice" in hm)
    print("dave" in hm)
    print(f"Size: {len(hm)}")

    hm.remove("bob")
    print(hm.get("bob"))
    print(f"Size after remove: {len(hm)}")

What does this test block do?

The if __name__ == "__main__" guard ensures this code only runs when you execute the file directly (not when importing from another file).

It exercises every method: put to store contacts, get to retrieve them, in to check membership, len for count, and remove to delete.

  • Save hash_map.py.
  • Run the file by executing this in your terminal:
python hash_map.py

You should see this output:

{'phone': '555-0001'}
{'phone': '555-0002'}
True
False
Size: 3
None
Size after remove: 2

Not seeing the expected output?

  • If you see NameError: name '_resize' is not defined, check that _resize is indented inside the class (4 spaces from the left edge).
  • If the test block runs but prints nothing, make sure the if __name__ line has zero indentation (it's outside the class).
  • If your output shows different dictionary ordering, that's fine. Python dictionaries inside the test data may display in any order.

Still stuck? Help me debug my HashMap test output

Why does hash() give different bucket positions each time you restart Python?

Python randomizes hash values for strings on each interpreter startup (since Python 3.3) as a security feature. This means the same key might land in different buckets across runs. Your HashMap still works correctly because it only needs consistent hashing within a single run.

✔️ Awesome, I've got everything!

Great. Double check you've saved hash_map.py and your test output matches.

ⓧ I'd like to double check the full code

Here's the complete hash_map.py for comparison:

class HashMap:
    def __init__(self, size=8):
        self._size = size
        self._buckets = [[] for _ in range(self._size)]
        self._count = 0

    def _hash(self, key):
        return hash(key) % self._size

    def put(self, key, value):
        if self._count / self._size >= 0.7:
            self._resize()

        index = self._hash(key)
        bucket = self._buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return

        bucket.append((key, value))
        self._count += 1

    def get(self, key):
        index = self._hash(key)
        bucket = self._buckets[index]

        for k, v in bucket:
            if k == key:
                return v
        return None

    def remove(self, key):
        index = self._hash(key)
        bucket = self._buckets[index]

        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._count -= 1
                return True
        return False

    def __contains__(self, key):
        return self.get(key) is not None

    def __len__(self):
        return self._count

    def keys(self):
        all_keys = []
        for bucket in self._buckets:
            for k, v in bucket:
                all_keys.append(k)
        return all_keys

    def _resize(self):
        old_buckets = self._buckets
        self._size *= 2
        self._buckets = [[] for _ in range(self._size)]
        self._count = 0

        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)


if __name__ == "__main__":
    hm = HashMap()
    hm.put("alice", {"phone": "555-0001"})
    hm.put("bob", {"phone": "555-0002"})
    hm.put("charlie", {"phone": "555-0003"})

    print(hm.get("alice"))
    print(hm.get("bob"))
    print("alice" in hm)
    print("dave" in hm)
    print(f"Size: {len(hm)}")

    hm.remove("bob")
    print(hm.get("bob"))
    print(f"Size after remove: {len(hm)}")

Your HashMap is complete. Next up, you'll build a Stack that powers an undo system for every action in your Contact Manager.

Build the Stack

Your HashMap gives you instant lookups. But what happens when a user accidentally deletes a contact and wants it back?

You need a way to remember the history of actions and reverse them. A Stack is the perfect structure for this. It follows the LIFO principle (Last In, First Out), meaning the most recent action is always the first one you can undo.

In this step, get ready to:
  • Build a Stack class with push and pop operations.
  • Add peek, is_empty, and length utilities and test the Stack.
Create the Stack class with push and pop

A Stack is one of the simplest data structures. It works like a stack of plates: you can only add to the top, and you can only remove from the top. This makes it ideal for tracking history.

  • Open stack.py in VS Code and add the following code:
class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()

    def is_empty(self):
        return len(self._items) == 0

What does this code do?

The Stack class uses a plain Python list (self._items) as its internal storage.

  • push(item) appends to the end of the list. This is the "top" of the stack.
  • pop() removes and returns the last item. If the stack is empty, it raises an IndexError so you know immediately something went wrong.
  • is_empty() is a helper that pop() uses to guard against removing from an empty stack.
  • Save stack.py.

You won't see any output yet. The next chunk adds a test block that runs the Stack through its paces.

Seeing a red underline in VS Code?

  • Check your indentation. Every method must be indented one level inside the class Stack: block.
  • Make sure is_empty is defined in the class. The pop() method calls it, so Python will complain if it is missing.

Help me fix indentation errors in my Stack class.

Add peek, is_empty, and len

The core push/pop operations are done. Now you need a way to look at the top item without removing it, and a way to check the stack's size.

  • In stack.py, add the following code below the is_empty method:
    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]

    def __len__(self):
        return len(self._items)


if __name__ == "__main__":
    s = Stack()
    s.push("first")
    s.push("second")
    s.push("third")

    print(s.peek())
    print(s.pop())
    print(s.pop())
    print(f"Size: {len(s)}")
    print(f"Empty: {s.is_empty()}")

What does this code do?

  • peek() returns the top item (self._items[-1]) without removing it. Useful for checking what the last action was before deciding whether to undo.
  • __len__ lets you call len(stack) just like you would on a list.
  • The if __name__ == "__main__" block runs a quick test. It pushes three items, peeks, pops twice, then checks the size.
  • Save stack.py.
  • Run your Stack by entering this command in the terminal:
python stack.py
  • You should see this output:
third
third
second
Size: 1
Empty: False

Why does "third" appear twice?

The first third comes from peek(), which looks at the top without removing it. The second third comes from pop(), which removes and returns it. That is exactly LIFO in action.

Seeing an IndexError or different output?

  • If you see IndexError: Stack is empty unexpectedly, check that push() uses self._items.append(item) and not self._items = item.
  • If you see a NameError, make sure peek and __len__ are indented inside the Stack class, not at the module level.

Help me debug my Stack output.

✔️ Awesome, I've got everything!

Great. Double check you've saved stack.py and confirmed your output matches.

ⓧ I'd like to double check the full code

Here is the complete stack.py file. Make sure yours matches exactly.

class Stack:
    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0

    def __len__(self):
        return len(self._items)


if __name__ == "__main__":
    s = Stack()
    s.push("first")
    s.push("second")
    s.push("third")

    print(s.peek())
    print(s.pop())
    print(s.pop())
    print(f"Size: {len(s)}")
    print(f"Empty: {s.is_empty()}")

Your Stack is ready to power an undo system. Next up, you'll build the third and final data structure: a Binary Search Tree that keeps everything sorted.

Build the Binary Search Tree

Your HashMap gives instant lookups and your Stack tracks history. But neither can answer the question: "show me all contacts between D and G, in alphabetical order." That requires sorted storage with efficient range access.

A Binary Search Tree solves this by organizing data so that every node's left children are smaller and right children are larger. This structure lets you find, insert, or delete any item in O(log n) time and retrieve sorted ranges without scanning everything.

In this step, get ready to:
  • Build a Node class and BST with recursive insert.
  • Implement search and delete (handling all three deletion cases).
  • Add inorder traversal and range search, then test the full tree.
Create the Node class and BST with insert

Every tree is made of nodes. Each node holds a key (the contact name), a value (the contact data), and two pointers: one to its left child and one to its right child.

  • In VS Code, open bst.py and add the Node class by pasting the following code:
class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        # Left child holds keys smaller than this node
        self.left = None
        # Right child holds keys larger than this node
        self.right = None

What does this code do?

A Node is the building block of the tree. It stores data (key and value) plus references to its two children.

Setting left and right to None means a new node starts as a leaf with no children.

Now you need the tree itself. The BinarySearchTree class manages the root node and provides all the operations.

  • Below the Node class, add the BinarySearchTree class with its insert method by pasting this code:


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

    def insert(self, key, value):
        # If tree is empty, the new node becomes the root
        if self.root is None:
            self.root = Node(key, value)
        else:
            self._insert_recursive(self.root, key, value)

    def _insert_recursive(self, node, key, value):
        # Smaller keys go left
        if key < node.key:
            if node.left is None:
                node.left = Node(key, value)
            else:
                self._insert_recursive(node.left, key, value)
        # Larger keys go right
        elif key > node.key:
            if node.right is None:
                node.right = Node(key, value)
            else:
                self._insert_recursive(node.right, key, value)
        # Duplicate key: update the value
        else:
            node.value = value

What does this code do?

The insert method places each new node in the correct position by comparing keys. If the new key is smaller than the current node, it goes left. If larger, it goes right.

The _insert_recursive helper walks down the tree until it finds an empty spot. If the key already exists, it updates the value instead of creating a duplicate.

  • Save bst.py.

Seeing a syntax error?

Make sure there is a blank line between the end of the Node class and the start of the BinarySearchTree class. Python needs that separation between top-level class definitions.

Also check that _insert_recursive is indented inside the BinarySearchTree class, not at the top level.

Help me debug my BST insert method

Implement search and delete

Searching a BST follows the same left/right logic as insert. Deletion is trickier because removing a node with two children requires finding a replacement that keeps the tree valid.

  • In bst.py, add the search methods inside the BinarySearchTree class, below _insert_recursive:
    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        # Base case: key not found
        if node is None:
            return None
        # Found the key
        if key == node.key:
            return node.value
        # Key is smaller, search left subtree
        elif key < node.key:
            return self._search_recursive(node.left, key)
        # Key is larger, search right subtree
        else:
            return self._search_recursive(node.right, key)

What does this code do?

The search method navigates left or right at each node based on whether the target key is smaller or larger. It returns the value if found, or None if it reaches an empty spot.

This is why BSTs are fast. Instead of checking every item, you eliminate half the remaining nodes at each step.

  • Save bst.py.
  • Now add the delete methods and the _find_min helper below your search methods:
    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return None

        # Navigate to the node to delete
        if key < node.key:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.key:
            node.right = self._delete_recursive(node.right, key)
        else:
            # Case 1 & 2: Node has zero or one child
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            # Case 3: Node has two children
            else:
                # Find the smallest node in the right subtree
                successor = self._find_min(node.right)
                node.key = successor.key
                node.value = successor.value
                # Delete the successor from its original position
                node.right = self._delete_recursive(node.right, successor.key)

        return node

    def _find_min(self, node):
        # The leftmost node is always the smallest
        current = node
        while current.left is not None:
            current = current.left
        return current

Why is delete so complex?

Deleting a node must preserve the BST property (left < parent < right). Three cases arise:

  • No children: simply remove the node.
  • One child: replace the node with its child.
  • Two children: find the in-order successor (smallest key in the right subtree), copy its data up, then delete the successor from its original spot.
  • Save bst.py.

Getting an AttributeError on delete?

Check that _delete_recursive returns node at the end of the method (outside the else block). Missing this return causes the parent to lose its reference to the subtree.

Help me debug my BST delete method

Add inorder traversal and range search

Traversal is how you visit every node in the tree. In-order traversal visits left, then the current node, then right. Because of the BST property, this naturally produces a sorted sequence.

  • In bst.py, add the inorder methods below _find_min:
    def inorder(self):
        results = []
        self._inorder_recursive(self.root, results)
        return results

    def _inorder_recursive(self, node, results):
        if node is not None:
            # Visit left subtree first (smaller keys)
            self._inorder_recursive(node.left, results)
            # Then current node
            results.append((node.key, node.value))
            # Then right subtree (larger keys)
            self._inorder_recursive(node.right, results)

What does this code do?

The left-root-right pattern is what makes in-order traversal special. Because every left subtree contains smaller keys and every right subtree contains larger keys, visiting in this order gives you a perfectly sorted list.

This is how your contact manager will display contacts alphabetically without ever calling a sort function.

  • Save bst.py.
  • Now add the range_search methods below _inorder_recursive:
    def range_search(self, low, high):
        results = []
        self._range_search_recursive(self.root, low, high, results)
        return results

    def _range_search_recursive(self, node, low, high, results):
        if node is None:
            return

        # Only visit left subtree if there might be keys >= low
        if node.key > low:
            self._range_search_recursive(node.left, low, high, results)

        # Include this node if it falls within the range
        if low <= node.key <= high:
            results.append((node.key, node.value))

        # Only visit right subtree if there might be keys <= high
        if node.key < high:
            self._range_search_recursive(node.right, low, high, results)

How does range search prune the tree?

Unlike inorder which visits every node, range search uses the BST property to skip entire subtrees. If the current node's key is already less than low, there is no point visiting its left subtree (all those keys are even smaller).

This pruning is what makes BST range queries faster than scanning a full list. The more of the tree you can skip, the faster the query.

  • Save bst.py.
  • Now add a test block at the bottom of the file (outside the class, with no indentation) to verify everything works:


if __name__ == "__main__":
    tree = BinarySearchTree()
    tree.insert("dave", {"phone": "555-0001"})
    tree.insert("alice", {"phone": "555-0002"})
    tree.insert("frank", {"phone": "555-0003"})
    tree.insert("bob", {"phone": "555-0004"})
    tree.insert("eve", {"phone": "555-0005"})

    # Should print names in alphabetical order
    print("Inorder:", [(k, v) for k, v in tree.inorder()])
    # Should find dave's phone
    print("Search dave:", tree.search("dave"))
    # Should return bob, dave, eve (between b and e)
    print("Range b-e:", tree.range_search("b", "e"))

    tree.delete("dave")
    # dave should be gone from the sorted list
    print("After delete dave:", [(k, v) for k, v in tree.inorder()])

What does this test verify?

  • Inorder traversal proves insert placed nodes correctly (you should see alphabetical order).
  • Search confirms you can retrieve a value by key.
  • Range search confirms the pruning logic works (only contacts between "b" and "e" are returned).
  • Delete confirms the two-children case works (dave has both a left and right subtree).
  • Save bst.py.
  • Run the file by executing this command in your terminal:
python bst.py
  • You should see four lines of output. The inorder list shows names in alphabetical order. The range search returns bob, dave, and eve. After deleting dave, the final inorder list shows four names without dave.

Seeing a RecursionError or wrong output?

A RecursionError usually means one of your recursive methods is missing its base case (if node is None: return). Double check that _search_recursive, _delete_recursive, and _range_search_recursive all handle the None case.

If your range search returns too many or too few results, check the comparison operators in _range_search_recursive. The condition low <= node.key <= high includes both boundaries.

Help me fix my BST output

✔️ Awesome, I've got everything!

Great. Double check you have saved bst.py and that all four print statements produced the expected output.

ⓧ I'd like to double check the full code

Here is the complete bst.py file. Compare yours against it:

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


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

    def insert(self, key, value):
        if self.root is None:
            self.root = Node(key, value)
        else:
            self._insert_recursive(self.root, key, value)

    def _insert_recursive(self, node, key, value):
        if key < node.key:
            if node.left is None:
                node.left = Node(key, value)
            else:
                self._insert_recursive(node.left, key, value)
        elif key > node.key:
            if node.right is None:
                node.right = Node(key, value)
            else:
                self._insert_recursive(node.right, key, value)
        else:
            node.value = value

    def search(self, key):
        return self._search_recursive(self.root, key)

    def _search_recursive(self, node, key):
        if node is None:
            return None
        if key == node.key:
            return node.value
        elif key < node.key:
            return self._search_recursive(node.left, key)
        else:
            return self._search_recursive(node.right, key)

    def delete(self, key):
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return None

        if key < node.key:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.key:
            node.right = self._delete_recursive(node.right, key)
        else:
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            else:
                successor = self._find_min(node.right)
                node.key = successor.key
                node.value = successor.value
                node.right = self._delete_recursive(node.right, successor.key)

        return node

    def _find_min(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current

    def inorder(self):
        results = []
        self._inorder_recursive(self.root, results)
        return results

    def _inorder_recursive(self, node, results):
        if node is not None:
            self._inorder_recursive(node.left, results)
            results.append((node.key, node.value))
            self._inorder_recursive(node.right, results)

    def range_search(self, low, high):
        results = []
        self._range_search_recursive(self.root, low, high, results)
        return results

    def _range_search_recursive(self, node, low, high, results):
        if node is None:
            return

        if node.key > low:
            self._range_search_recursive(node.left, low, high, results)

        if low <= node.key <= high:
            results.append((node.key, node.value))

        if node.key < high:
            self._range_search_recursive(node.right, low, high, results)


if __name__ == "__main__":
    tree = BinarySearchTree()
    tree.insert("dave", {"phone": "555-0001"})
    tree.insert("alice", {"phone": "555-0002"})
    tree.insert("frank", {"phone": "555-0003"})
    tree.insert("bob", {"phone": "555-0004"})
    tree.insert("eve", {"phone": "555-0005"})

    print("Inorder:", [(k, v) for k, v in tree.inorder()])
    print("Search dave:", tree.search("dave"))
    print("Range b-e:", tree.range_search("b", "e"))

    tree.delete("dave")
    print("After delete dave:", [(k, v) for k, v in tree.inorder()])

Your Binary Search Tree is complete. You now have three data structures: a HashMap for O(1) lookups, a Stack for undo history, and a BST for sorted access and range queries. Next up, you will wire all three together into a working Contact Manager CLI.

Build the Contact Manager CLI

You now have three powerful data structures sitting in separate files. Each one solves a different shape of problem: instant lookup, temporal history, and sorted access.

In this step, you will wire all three together into a single ContactManager class and build a command-line interface around it. This is where the payoff happens.

In this step, get ready to:
  • Create a ContactManager class that combines all three data structures.
  • Implement add, search, delete, list, range search, and undo operations.
  • Build a CLI menu loop and test the full application.
Create the ContactManager class

The ContactManager is the orchestration layer. It decides which data structure handles each operation so that every contact lives in the HashMap for fast lookup AND the Binary Search Tree for sorted access simultaneously.

  • In VS Code, open contact_manager.py and add the imports, class initialization, and first method by pasting this code:
from hash_map import HashMap
from stack import Stack
from bst import BinarySearchTree


class ContactManager:
    def __init__(self):
        self.contacts = HashMap()
        self.undo_stack = Stack()
        self.search_tree = BinarySearchTree()

    def add_contact(self, name, phone, email):
        contact = {"phone": phone, "email": email}
        key = name.lower()

        if key in self.contacts:
            print(f"Contact '{name}' already exists. Use a different name.")
            return

        self.contacts.put(key, contact)
        self.search_tree.insert(key, contact)
        self.undo_stack.push(("add", key, contact))
        print(f"Added contact: {name}")

What does this code do?

The imports pull in your three custom data structures from their respective files.

  • self.contacts = HashMap() stores contacts for O(1) average lookup by name.
  • self.undo_stack = Stack() records every action so you can reverse it later.
  • self.search_tree = BinarySearchTree() keeps contacts sorted alphabetically for listing and range queries.
  • add_contact stores the contact in both the HashMap and BST, then pushes the action onto the undo stack. Every write goes to both structures so they stay in sync.
  • Save contact_manager.py.

Seeing a red underline on the imports?

VS Code may show import errors if the Python interpreter is not set to the correct environment. Click the Python version in the bottom status bar and select the interpreter that matches your project folder.

Also confirm that hash_map.py, stack.py, and bst.py are all in the same contact-manager folder as contact_manager.py.

Help me debug my import errors in contact_manager.py

Implement search, delete, list, range search, and undo

Now you need the methods that let users interact with their stored contacts. Each method leverages a different data structure's strength.

  • Add the search_contact and delete_contact methods below add_contact by pasting this code:
    def search_contact(self, name):
        contact = self.contacts.get(name.lower())
        if contact:
            print(f"\n  Name:  {name}")
            print(f"  Phone: {contact['phone']}")
            print(f"  Email: {contact['email']}")
        else:
            print(f"Contact '{name}' not found.")

    def delete_contact(self, name):
        key = name.lower()
        contact = self.contacts.get(key)
        if contact is None:
            print(f"Contact '{name}' not found.")
            return

        self.contacts.remove(key)
        self.search_tree.delete(key)
        self.undo_stack.push(("delete", key, contact))
        print(f"Deleted contact: {name}")

What does this code do?

  • search_contact uses the HashMap's O(1) get to find a contact instantly by name.
  • delete_contact removes the contact from BOTH the HashMap and BST to keep them in sync. It also saves the deleted data onto the undo stack so the action can be reversed.
  • Now add the list_contacts, range_search, and undo methods below delete_contact by pasting this code:
    def list_contacts(self):
        sorted_contacts = self.search_tree.inorder()
        if not sorted_contacts:
            print("No contacts found.")
            return

        print(f"\n{'Name':<20} {'Phone':<15} {'Email'}")
        print("-" * 55)
        for name, contact in sorted_contacts:
            print(f"{name:<20} {contact['phone']:<15} {contact['email']}")

    def range_search(self, start, end):
        results = self.search_tree.range_search(start.lower(), end.lower())
        if not results:
            print(f"No contacts found between '{start}' and '{end}'.")
            return

        print(f"\nContacts from '{start}' to '{end}':")
        print(f"\n{'Name':<20} {'Phone':<15} {'Email'}")
        print("-" * 55)
        for name, contact in results:
            print(f"{name:<20} {contact['phone']:<15} {contact['email']}")

    def undo(self):
        if self.undo_stack.is_empty():
            print("Nothing to undo.")
            return

        action = self.undo_stack.pop()

        if action[0] == "add":
            key = action[1]
            self.contacts.remove(key)
            self.search_tree.delete(key)
            print(f"Undo: removed '{key}'")
        elif action[0] == "delete":
            key = action[1]
            contact = action[2]
            self.contacts.put(key, contact)
            self.search_tree.insert(key, contact)
            print(f"Undo: restored '{key}'")

What does this code do?

  • list_contacts calls the BST's inorder() traversal. Because the BST stores keys in sorted order, you get an alphabetical contact list for free.
  • range_search delegates to the BST's efficient range query. Only subtrees that could contain matching keys are visited.
  • undo pops the last action from the Stack and reverses it. If the last action was "add", it removes the contact. If it was "delete", it restores the contact. This is the LIFO principle in action.
  • Save contact_manager.py.

Indentation errors?

All these methods must be indented one level inside the ContactManager class (4 spaces). If you see IndentationError when you run the file later, check that no method is flush with the left margin.

Help me fix indentation errors in my ContactManager class

Build the CLI menu loop and test

The CLI is the user-facing layer that translates menu choices into ContactManager method calls. A simple while True loop keeps the program running until the user quits.

  • Add the main() function at the bottom of contact_manager.py, outside the class (no indentation), by pasting this code:
def main():
    manager = ContactManager()

    print("=" * 40)
    print("  CONTACT MANAGER")
    print("  Powered by Custom Data Structures")
    print("=" * 40)

    while True:
        print("\nCommands:")
        print("  1. Add contact")
        print("  2. Search contact")
        print("  3. Delete contact")
        print("  4. List all contacts (sorted)")
        print("  5. Range search")
        print("  6. Undo last action")
        print("  7. Quit")

        choice = input("\nEnter choice (1-7): ").strip()

        if choice == "1":
            name = input("Name: ").strip()
            phone = input("Phone: ").strip()
            email = input("Email: ").strip()
            manager.add_contact(name, phone, email)
        elif choice == "2":
            name = input("Name to search: ").strip()
            manager.search_contact(name)
        elif choice == "3":
            name = input("Name to delete: ").strip()
            manager.delete_contact(name)
        elif choice == "4":
            manager.list_contacts()
        elif choice == "5":
            start = input("Start letter/name: ").strip()
            end = input("End letter/name: ").strip()
            manager.range_search(start, end)
        elif choice == "6":
            manager.undo()
        elif choice == "7":
            print("Goodbye!")
            break
        else:
            print("Invalid choice. Please enter 1-7.")


if __name__ == "__main__":
    main()

What does this code do?

  • main() creates a ContactManager instance and enters an infinite loop that prints a menu, reads the user's choice, and dispatches to the matching method.
  • Each menu option maps to exactly one ContactManager method. The CLI handles user input (prompts, stripping whitespace) so the class methods stay clean.
  • if __name__ == "__main__": ensures the menu only runs when you execute the file directly, not when another file imports it.
  • Save contact_manager.py.
  • Run the Contact Manager by executing this command in your terminal:
python contact_manager.py
  • You should see the CONTACT MANAGER banner and a numbered menu of 7 options.
  • Test the app by adding a few contacts. Enter 1 to add, then type a name, phone, and email when prompted.
  • Try option 2 to search for a contact you just added.
  • Try option 4 to list all contacts in alphabetical order.
  • Try option 5 with a start of a and end of d to see range search in action.
  • Try option 6 to undo your last action. You should see the last contact you added get removed.
  • Enter 7 to quit when you are done testing.

Seeing ModuleNotFoundError?

Make sure your terminal is inside the contact-manager folder. Run ls and confirm you can see hash_map.py, stack.py, bst.py, and contact_manager.py in the output. If not, cd into the correct folder and try again.

Help me fix ModuleNotFoundError when running contact_manager.py

✔️ Awesome, I've got everything!

Great. Double check you have saved contact_manager.py and your CLI responds to all 7 menu options.

ⓧ I'd like to double check the full code

Here is the complete contact_manager.py for comparison.

from hash_map import HashMap
from stack import Stack
from bst import BinarySearchTree


class ContactManager:
    def __init__(self):
        self.contacts = HashMap()
        self.undo_stack = Stack()
        self.search_tree = BinarySearchTree()

    def add_contact(self, name, phone, email):
        contact = {"phone": phone, "email": email}
        key = name.lower()

        if key in self.contacts:
            print(f"Contact '{name}' already exists. Use a different name.")
            return

        self.contacts.put(key, contact)
        self.search_tree.insert(key, contact)
        self.undo_stack.push(("add", key, contact))
        print(f"Added contact: {name}")

    def search_contact(self, name):
        contact = self.contacts.get(name.lower())
        if contact:
            print(f"\n  Name:  {name}")
            print(f"  Phone: {contact['phone']}")
            print(f"  Email: {contact['email']}")
        else:
            print(f"Contact '{name}' not found.")

    def delete_contact(self, name):
        key = name.lower()
        contact = self.contacts.get(key)
        if contact is None:
            print(f"Contact '{name}' not found.")
            return

        self.contacts.remove(key)
        self.search_tree.delete(key)
        self.undo_stack.push(("delete", key, contact))
        print(f"Deleted contact: {name}")

    def list_contacts(self):
        sorted_contacts = self.search_tree.inorder()
        if not sorted_contacts:
            print("No contacts found.")
            return

        print(f"\n{'Name':<20} {'Phone':<15} {'Email'}")
        print("-" * 55)
        for name, contact in sorted_contacts:
            print(f"{name:<20} {contact['phone']:<15} {contact['email']}")

    def range_search(self, start, end):
        results = self.search_tree.range_search(start.lower(), end.lower())
        if not results:
            print(f"No contacts found between '{start}' and '{end}'.")
            return

        print(f"\nContacts from '{start}' to '{end}':")
        print(f"{'Name':<20} {'Phone':<15} {'Email'}")
        print("-" * 55)
        for name, contact in results:
            print(f"{name:<20} {contact['phone']:<15} {contact['email']}")

    def undo(self):
        if self.undo_stack.is_empty():
            print("Nothing to undo.")
            return

        action = self.undo_stack.pop()

        if action[0] == "add":
            key = action[1]
            self.contacts.remove(key)
            self.search_tree.delete(key)
            print(f"Undo: removed '{key}'")
        elif action[0] == "delete":
            key = action[1]
            contact = action[2]
            self.contacts.put(key, contact)
            self.search_tree.insert(key, contact)
            print(f"Undo: restored '{key}'")


def main():
    manager = ContactManager()

    print("=" * 40)
    print("  CONTACT MANAGER")
    print("  Powered by Custom Data Structures")
    print("=" * 40)

    while True:
        print("\nCommands:")
        print("  1. Add contact")
        print("  2. Search contact")
        print("  3. Delete contact")
        print("  4. List all contacts (sorted)")
        print("  5. Range search")
        print("  6. Undo last action")
        print("  7. Quit")

        choice = input("\nEnter choice (1-7): ").strip()

        if choice == "1":
            name = input("Name: ").strip()
            phone = input("Phone: ").strip()
            email = input("Email: ").strip()
            manager.add_contact(name, phone, email)
        elif choice == "2":
            name = input("Name to search: ").strip()
            manager.search_contact(name)
        elif choice == "3":
            name = input("Name to delete: ").strip()
            manager.delete_contact(name)
        elif choice == "4":
            manager.list_contacts()
        elif choice == "5":
            start = input("Start letter/name: ").strip()
            end = input("End letter/name: ").strip()
            manager.range_search(start, end)
        elif choice == "6":
            manager.undo()
        elif choice == "7":
            print("Goodbye!")
            break
        else:
            print("Invalid choice. Please enter 1-7.")


if __name__ == "__main__":
    main()

Your Contact Manager is fully operational. You have three custom data structures working together in a single application, each handling the problem it was designed for. Next up, you will take on the Secret Mission and extend your BST with prefix search for autocomplete.

Secret mission

Add Prefix Search (Autocomplete)

Your contact manager can find exact names and range-search alphabetically. But what about autocomplete? Add a prefix search so typing "da" finds "daniel", "dave", and "darren" instantly. This teaches a new BST traversal pattern that powers search bars everywhere.

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your project files or delete them.

Resources you used:

  • The contact-manager folder on your Desktop (contains hash_map.py, stack.py, bst.py, contact_manager.py).

Keep everything running

No action needed. Choose this if you want to keep building on your data structures or extend the Contact Manager with new features.

  • Your contact-manager folder stays on your Desktop, ready to open any time.
  • Run python contact_manager.py from inside the folder whenever you want to use your app.

Pause - I'll come back to this later

Since this is a local-only project with no running processes, there is nothing to pause. Your files sit on disk and use negligible storage.

  • Close the contact-manager folder in VS Code to free up your workspace.
  • Your files will be waiting on your Desktop whenever you want to return.

Delete - I don't want to use this again

Remove all project files from your machine.

  • Close the contact-manager folder in VS Code.
  • Delete the project folder by running this command in your terminal (macOS/Linux):
rm -rf ~/Desktop/contact-manager

On Windows, run this in PowerShell instead:

Remove-Item -Recurse -Force ~\Desktop\contact-manager
  • Confirm the folder is gone by checking your Desktop. You should no longer see contact-manager listed.

Nice Work!

Nice Work!

You just built three fundamental data structures from scratch and wired them into a working Contact Manager application. No libraries, no shortcuts. Just pure Python and your understanding of how data wants to be organized.

You've learned how to:

  • Build a Hash Map from scratch with hashing, collision handling via chaining, and dynamic resizing. You now understand how Python's dict achieves O(1) average lookups under the hood.
  • Build a Stack-powered undo system using the LIFO principle. The same pattern powers browser back buttons, Ctrl+Z in every editor, and function call stacks.
  • Build a Binary Search Tree with recursive insert, delete, in-order traversal, and range queries. You wired all three structures into a working Contact Manager CLI that proves these aren't just textbook concepts.
  • Extend the BST with prefix search (autocomplete), the same idea behind search bars and IDE suggestions.

Ready to quiz yourself?