Debugging lab: trie bugs

Why this matters

A trie bug often does not look like a crash at first. A program may print False for a word you just inserted, and nothing stops. Or it may work for most words and then fail on one word that contains the letter z. Reading the code and guessing is slow. Running the program, reading the exact output, and matching that output to one line is faster.

This lab gives you three small programs. Each one fails in a different way.

• A missing end flag: the path for a word exists, but the last node is not marked as the end of a word, so a search for that word returns False.
• A wrong letter index: the code turns a letter into a list position with the wrong formula, so the lookup goes past the end of the list.
• A missing child: the code follows a link that was never created, then reads an attribute from nothing.

The earlier lessons in this module cover the node design, insert and search, and the wildcard search. This lab assumes you know what a node is. It only asks you to find the fault and fix it.

The four steps

Use the same four steps as in the other labs of this course.

1. Write down what you expect the program to print.
2. Run it, and copy the exact output.
3. Find the first output line that differs from your expectation.
4. Find the line of code that causes the difference, and say why in one sentence.

Some terms help when you read the output.

• A trie is a tree where each step down adds one letter. The word cat is the path root, then c, then a, then t.
• A node is one box in the tree. In these programs a node holds its children and one True or False flag.
• A child is the node one step down for one letter. A child slot is a place that can hold a child, or hold None when no child exists yet.
• The end flag (is_end in the code) is True on the node where a stored word stops. Without it, a trie cannot tell cat from ca when both paths exist.
• An index is a whole number that picks one slot in a list. Index 0 is the first slot. A list of length 26 has indexes 0 to 25.
• None means "no object". A variable that holds None has no node behind it.
• A traceback is the list of lines Python prints after an error. The last line names the error, and the lines above it show the calls that led to it, with the line numbers. Python also draws small arrows under the part of the line that failed.

Most of the programs store children in a list, [None] * 26, which has one slot for each lowercase letter. The first program uses a dictionary instead, so its code looks different.

Save each program as main.py and run it with python3 main.py. The line numbers in the output are the numbers in your file, so they match the programs below only if you copy them exactly. The output in this lab comes from Python 3.14.4.

Case 1: the word that is in the trie but not found

The program below stores the children of each node in a dictionary, a Python table that maps each one-letter string to a Node. The insert method walks down the path and creates the nodes it needs. It never marks the last node as the end of a word.

class Node:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
 
class Trie:
    def __init__(self):
        self.root = Node()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = Node()
            node = node.children[ch]
 
    def search(self, word):
        node = self.root
        for ch in word:
            node = node.children.get(ch)
            if node is None:
                return False
        return node.is_end
 
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return False
        return True
 
 
trie = Trie()
trie.insert("cat")
print("search cat:", trie.search("cat"))
print("search ca:", trie.search("ca"))
print("starts with ca:", trie.starts_with("ca"))

The expected output is search cat: True on the first line, because the program inserted cat. Run it and read the result.

search cat: False
search ca: False
starts with ca: True

The first line differs from the expectation. Look at the second and third lines first, because they tell you what is in the trie. starts_with("ca") prints True, so the path c then a exists. search("cat") walks that same path and then reads the flag on the last node. The path is correct, and the flag is False.

The cause is the end of insert. The loop creates the nodes, and then the method returns. Nothing sets is_end on the node for t. The fix is one line after the loop.

        node.is_end = True

Put that line after the loop, at the same indent as the for line, and before the method ends. The fixed program prints this:

search cat: True
search ca: False
starts with ca: True

search("ca") still prints False, and that is correct. The a node exists, but no word ends there, so its flag stays False. A prefix such as ca is found by starts_with, and only a full stored word is found by search.

This bug makes no noise. There is no exception and no crash. A test that only checks a word that was never inserted will pass, and the bug will stay hidden. When you test a trie, insert a word and then search for that same word. A failed search for an inserted word is the sign of this bug.

Case 2: the letter that lands outside the list

When children are stored in a list of 26 slots, each letter needs a position from 0 to 25. The position is the distance from the letter a. In Python, ord gives the number that stands for a character. The letter a has the number 97, c has 99, and the uppercase A has 65. So ord("c") - ord("a") is 99 minus 97, which is 2. The letter a gives 0 and the letter z gives 25.

Part 1: subtracting the wrong base letter

The next program has the same shape as Case 1, but it uses a list. The index formula subtracts the uppercase "A".

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def index(ch):
    return ord(ch) - ord("A")
 
 
def insert(root, word):
    node = root
    for ch in word:
        idx = index(ch)
        if node.children[idx] is None:
            node.children[idx] = Node()
        node = node.children[idx]
    node.is_end = True
 
 
root = Node()
insert(root, "cat")
print("inserted cat")

The expected output is inserted cat. The real output is an error.

Traceback (most recent call last):
  File "main.py", line 22, in <module>
    insert(root, "cat")
    ~~~~~~^^^^^^^^^^^^^
  File "main.py", line 15, in insert
    if node.children[idx] is None:
       ~~~~~~~~~~~~~^^^^^
IndexError: list index out of range

The class name IndexError says that an index is outside the list. The message does not give the bad index, so read the line the traceback names. The line if node.children[idx] is None: is line 15, and the arrows point at node.children[idx], the part that used the index. The index is idx, which comes from index(ch) on line 14.

Where does 34 come from? The first letter of cat is c, which is 99. Subtract ord("A"), which is 65, and the result is 34. Every lowercase letter minus 65 gives a number from 32 to 57, and all of those are past the end of a 26-slot list. Python checks each index before it reads the slot, and it stops with this error rather than reading a slot that is not in the list.

The fix is to subtract ord("a").

def index(ch):
    return ord(ch) - ord("a")

With that change the program prints inserted cat.

Python has a second trap here that Java does not have. A capital letter gives a negative index with ord(ch) - ord("a"). Python counts negative indexes from the end of the list, so T (index -13) quietly reads slot 13 with no error. A (index -32) is out of range and raises IndexError. Convert words to lowercase before you use them, as the earlier lessons of this module do.

Part 2: the formula that fails only on z

A common attempt to avoid slot 0 is to add one, so the letters take slots 1 to 26 and slot 0 stays empty. The formula becomes ord(ch) - ord("a") + 1. This version has a search function too, so the program can check its own work.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def index(ch):
    return ord(ch) - ord("a") + 1
 
 
def insert(root, word):
    node = root
    for ch in word:
        idx = index(ch)
        if node.children[idx] is None:
            node.children[idx] = Node()
        node = node.children[idx]
    node.is_end = True
 
 
def search(root, word):
    node = root
    for ch in word:
        node = node.children[index(ch)]
        if node is None:
            return False
    return node.is_end
 
 
root = Node()
insert(root, "cat")
print("search cat:", search(root, "cat"))
insert(root, "zoo")
print("search zoo:", search(root, "zoo"))

The output is this.

search cat: True
Traceback (most recent call last):
  File "main.py", line 33, in <module>
    insert(root, "zoo")
    ~~~~~~^^^^^^^^^^^^^
  File "main.py", line 15, in insert
    if node.children[idx] is None:
       ~~~~~~~~~~~~~^^^^^
IndexError: list index out of range

The first line is correct. insert and search both use the same index function, so they agree with each other for cat. The second word fails. The letter z is 25 in the correct formula, and adding 1 makes it 26. Index 26 is outside a 26-slot list.

This version passes any quick test that uses only words without z. The bug appears only for the last letter of the alphabet, so test a word that contains z. The fix is the same as in Part 1: remove the + 1, so the formula is ord(ch) - ord("a"). The fixed version prints this:

search cat: True
search zoo: True

Case 3: the missing child

A missing child is a link that was never made. In a list trie, node.children[idx] is None until some word has used that letter at that position. Code that follows the link without checking it will fail when the link is missing.

Part 1: following a link that was never made

The next program walks down the list for each letter, but it never creates a missing child.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def insert(root, word):
    node = root
    for ch in word:
        node = node.children[ord(ch) - ord("a")]
    node.is_end = True
 
 
root = Node()
insert(root, "cat")
print("inserted cat")

The output is this.

Traceback (most recent call last):
  File "main.py", line 15, in <module>
    insert(root, "cat")
    ~~~~~~^^^^^^^^^^^^^
  File "main.py", line 10, in insert
    node = node.children[ord(ch) - ord("a")]
           ^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'children'

The class AttributeError means the program asked a value for an attribute that it does not have. NoneType is the type of None, so the message says that a None was used where a node was expected. Python names the attribute, children, but it does not name the variable. The arrows point at node.children, and that tells you which variable held None.

Trace the first step. root.children[2] is None because the trie is empty. So node becomes None. The loop then starts the second letter, a, and tries to read node.children. That read fails on line 10.

The fix is to create the child when the slot is empty. This is the same idea as the if ... is None check in the Case 1 insert.

    for ch in word:
        idx = ord(ch) - ord("a")
        if node.children[idx] is None:
            node.children[idx] = Node()
        node = node.children[idx]

Part 2: a search that follows a missing link

A search must not create nodes, but it must stop when a link is missing. The next program inserts cat correctly. Its search walks the list and does not check for None before the next step.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def insert(root, word):
    node = root
    for ch in word:
        idx = ord(ch) - ord("a")
        if node.children[idx] is None:
            node.children[idx] = Node()
        node = node.children[idx]
    node.is_end = True
 
 
def search(root, word):
    node = root
    for ch in word:
        node = node.children[ord(ch) - ord("a")]
    return node.is_end
 
 
root = Node()
insert(root, "cat")
print("search cat:", search(root, "cat"))
print("search do:", search(root, "do"))

The output is this.

search cat: True
Traceback (most recent call last):
  File "main.py", line 27, in <module>
    print("search do:", search(root, "do"))
                        ~~~~~~^^^^^^^^^^^^
  File "main.py", line 20, in search
    node = node.children[ord(ch) - ord("a")]
           ^^^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'children'

The first line is correct. The second search fails. The root has no child for d, so after the letter d the variable node is None. The loop then runs for the letter o and reads node.children. The traceback line 20 is the line inside the loop.

The fix is to check for None after each step and return False when the path ends. The program with only the search changed prints the following:

search cat: True
search do: False

Here is the fixed search function, which replaces the one above.

def search(root, word):
    node = root
    for ch in word:
        node = node.children[ord(ch) - ord("a")]
        if node is None:
            return False
    return node.is_end

Part 3: the same bug on the last line

A missing check can fail on a different line than you expect. The next function does the search with no None check at all, and it is called with a one-letter word.

def search_last(root, word):
    node = root
    for ch in word:
        node = node.children[ord(ch) - ord("a")]
    return node.is_end

Called with cat, it returns True. Called with d, the loop runs once. The root has no child for d, so node becomes None. The loop ends, and the function reads node.is_end on the return line. This output comes from a program that calls search_last with cat and then d, after inserting cat.

search_last cat: True
Traceback (most recent call last):
  File "main.py", line 27, in <module>
    print("search_last d:", search_last(root, "d"))
                            ~~~~~~~~~~~^^^^^^^^^^^
  File "main.py", line 21, in search_last
    return node.is_end
           ^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'is_end'

The message says is_end instead of children, and the line is the return line. A longer word such as do fails inside the loop instead. The cause is the same missing check. Add the check inside the loop, as in the fixed search from Part 2. Then search_last("d") returns False.

Common mistakes

These are the mistakes that appear most often in trie code. Each one has a visible sign.

• No end flag: insert builds the path but never sets is_end. Sign: search returns False for words that were inserted, while starts_with returns True. There is no error message.
• Wrong base letter: the index uses "A" or some other base. Sign: IndexError with a list index that is past the end, such as 34, on the line that uses the index. A capital letter with a lowercase base gives a negative index. Python reads some of these from the end of the list with no error, and raises IndexError for others.
• Off by one: the index adds a number, such as ord(ch) - ord("a") + 1. Sign: all words pass until one contains z, which gives index 26 and the same IndexError.
• Missing child on insert: insert moves to node.children[idx] without creating it. Sign: AttributeError: 'NoneType' object has no attribute 'children' or 'is_end', on the line that reads a child or sets the flag.
• Missing None check on search: the search follows a link without checking it. Sign: AttributeError in search, with NoneType in the message.
• Search that creates nodes: some code creates children inside search by mistake. Then searching changes the trie, so a check that inserts and searches the same word can no longer show whether insert is correct. Searches should only read the trie.

Practice

Exercise 1. The program in Case 1 has no fix yet. After inserting car and ca with the buggy insert, what does search("ca") print?

Show the answer: It prints False. The buggy insert never sets is_end on any node, so every search call returns False. Only starts_with can return True in that program.

Exercise 2. In the Case 2 Part 2 program, which letters cause an error, and what index does each one produce?

Show the answer: Only z does. With ord(ch) - ord("a") + 1, z gives 25 plus 1, which is index 26. Every other letter gives an index from 1 to 25, which fits in a 26-slot list.

Exercise 3. A trie stores children in a list of 26. What index does the correct formula ord(ch) - ord("a") give for the letter m?

Show the answer: It gives 12. The letter m is 109 in Python's numbering, a is 97, and 109 minus 97 is 12. The letter m is the 13th letter of the alphabet, and index 12 is the 13th slot.

Exercise 4. The fixed search from Case 2 Part 2 is used on a trie that holds only cat. What does search("ca") return?

Show the answer: It returns False. The nodes for c and a exist, so the loop finishes without a None check failing. The node for a has no end flag, because no stored word ends at ca. So node.is_end is False.

Exercise 5. The search_last function from Case 3 Part 3 fails on d. Write the change that makes search_last("d") return False and keeps every other result the same.

Show the answer: Add a None check inside the loop, right after the line that moves node to the child. The loop body becomes node = node.children[ord(ch) - ord("a")] followed by if node is None: return False. This is the same change as the fixed search in Part 2.

Summary

• A missing end flag makes search return False for a word that is in the trie, while starts_with still finds its path. Set is_end = True at the end of insert.
• For lowercase letters, the index formula must be ord(ch) - ord("a"). Subtracting "A" gives indexes past 25, and adding 1 fails only on z.
• A missing child is a link that was never created. Create it in insert, and check for None in search before the next step.
• Python's AttributeError for a None value names the attribute that was read, and the arrows under the line show the expression. Find the variable in that expression first.
• When testing a trie, insert a word and search for it, and include a word that contains z.