Trie structure, insert and search

Why this matters

Your phone suggests the next word while you type. A search box finishes "prog" into "programming" before you press a key. A spell checker asks whether any dictionary word begins with the letters typed so far. All three ask a prefix question: "which stored words begin with these letters?" A data structure called a trie (pronounced "try") answers that question directly. It is one of the few structures that can answer prefix questions in time that depends on the length of the letters you typed, not on how many words are stored.

This lesson builds the basic trie in C++. You will write the node type, insert words, search for whole words, check prefixes, count nodes, and validate input. Later lessons add autocomplete, counting, deletion and interview problems. Everything here is needed for those.

Start with the problem, not the tree

Suppose you must store a dictionary of 100,000 English words and answer two questions quickly:

1. Is this exact word in the dictionary?
2. Does any word in the dictionary start with these letters?

The first question is easy with a hash set. A hash set (in C++ std::unordered_set<string>) turns a word into a number and jumps to a bucket, so an exact check costs about the length of the word. A hash is a rule that turns a value into a number used as an address, and a bucket is one slot where values with the same number are kept.

The second question is hard with a hash set. A hash set has no order and no idea which words share a beginning. To answer "does any word start with pr?", you must look at every word, one at a time. With 100,000 words that is 100,000 comparisons for each keystroke. Each comparison may read several characters, so the work grows quickly.

A sorted array helps with prefixes. All words that start with "pr" sit next to each other, so you can binary search for the first one, then read forward while the letters still match. Binary search means checking the middle item, then discarding half, and repeating. But inserting a new word into a sorted array means moving every word after it one place to the right. Many inserts become slow, and the array must be re-sorted if you add words in a random order.

A trie avoids both problems. It stores words so that words with the same beginning share the same path. The words "prefix" and "print" both start with p and r, so those two letters are stored once. A prefix question becomes a walk down the structure: take one step per letter. If the walk succeeds, at least one stored word has that beginning. If a step is missing, no stored word does.

Before writing any code, hold on to this picture. A trie trades memory for speed on prefix work. Every decision in this lesson exists to make that trade clear.

The analogy: a filing cabinet with nested folders

Imagine a filing cabinet for customer letters. The top drawer is labelled with the first letter of the customer's name: A, B, C and so on. Inside the C drawer there is a second level of folders, one per second letter: Ca, Ce, Ci and so on. Inside the Ca folder there are folders for the third letter, and so on. A name is found by opening one drawer after another, one letter at a time, until you reach the folder for the whole name.

The cabinet has two more rules that matter for a trie.

First, a folder for "Car" might hold the letter for the customer Car, and it might also contain a deeper folder "Card" for another customer. A folder can be both a stored name and a stepping stone to longer names. You need a label on the folder that says "a name ends here" to tell these apart.

Second, if you open a drawer and find nothing inside, no customer has that beginning. You can stop searching at once. This second rule is what makes prefix questions fast. You never look at the names that do not match.

A trie is that cabinet, built in memory. Each folder is a node. Each drawer is an edge, labelled with one letter. The top folder is the root. A word is the path of letters from the root down to a folder. A flag on a folder tells you whether a stored word ends there.

Vocabulary before code

Several terms will come up in every lesson of this module, so define them now.

• Node: one box in the tree. It holds links to its children and a flag.
• Root: the top node. It stands for the empty string, so it has no letter of its own.
• Edge: a link from a parent node to a child node. In a trie, each edge is labelled with one letter.
• Child: the node at the other end of an edge. The child of the root along the letter c is the node you reach after the letter c.
• Parent: the node at the top of an edge. Every node except the root has exactly one parent.
• Leaf: a node with no children. A leaf always ends a word, because otherwise it would have no reason to exist.
• Word end: a node where a stored word stops. In our code this is the boolean flag isEnd.
• Prefix: the first few letters of a word. "ca" is a prefix of "car" and of "card". The empty string is a prefix of every word.
• Path: the sequence of nodes you pass from the root to a given node. For the node reached by "car", the path is root, c, a, r.

A word can end in the middle of the tree. That is why the flag matters. In a trie holding car and card, the node for "car" is both a word end and a node on the way to "card". Without the flag you could not tell whether "car" was stored or only a prefix of something longer.

Why a trie is a tree

A trie is a special kind of tree. In a tree, each node has at most one parent, and there are no loops, so you can never come back to a node by following edges. A trie has these properties because every new letter goes deeper. The root has no parent. Every other node has exactly one parent, the node for the letters before its last one.

The picture below is a trie for the words car, card, care and cat. Read it from the top. The shared path c, a is stored once. Below the r node the tree splits into d (for card) and e (for care), and cat branches from a.

Trie for car, card, care and cat: the shared letters c and a sit on one path, and the words split below them

The Viz below shows a binary tree walked in a fixed order. The walk you do on a trie follows the same idea: start at the root, visit a child, then continue. Step through the animation, then notice that each node's children appear below it, just as each trie node's letters lead to deeper nodes.

What makes a trie different from the binary tree in the animation is the branching. A binary node has two children. A trie node can have up to 26 children, one for each lowercase letter. That number is what the rest of this lesson builds on.

The node in C++

A node needs two things: links to its children, and a flag for whether a word ends at this node. Here is the smallest version that works.

struct Node {
    Node* next[26] = {};
    bool isEnd = false;
};

Read it piece by piece.

• struct Node declares a new type named Node. A struct groups related data. Here it groups the links and the flag.
• Node* next[26] declares an array of 26 pointers. A pointer holds the memory address of a Node, or the special value nullptr, which means "points at nothing". The name next is only a label. You could call it child, and many codebases do.
• The index 0 stands for 'a', 1 for 'b', and so on up to 25 for 'z'. A pointer in slot i means "there is a road for letter i from this node".
• = {} gives every pointer the value nullptr. This matters. An array of pointers that you do not initialise holds whatever bytes happened to be in memory, and those bytes can look like real addresses. A trie node built with new and not initialised can therefore point at garbage, and the first walk over it crashes or gives wrong answers.
• bool isEnd = false; starts the flag as false. A brand-new node is not the end of a word.

Each node is a fixed size: 26 pointers plus one boolean. On a typical 64-bit machine a pointer takes 8 bytes, so the child array takes 208 bytes. The flag takes one byte, and the compiler usually pads the struct so the whole node is 216 bytes. That is far larger than a single letter, which is why tries can use a lot of memory. We return to that trade-off near the end of this lesson and again in lesson four.

The picture below shows one node. Most of its 26 slots are empty. The slots that hold addresses point at the next node on a road. The flag sits beside them.

A trie node: 26 child slots, most of them empty, plus one word-end flag

What new does

To create a node we write new Node(). The new keyword asks the runtime for a block of memory on the heap, which is the area of memory that lives until you release it. It returns the address of that block. The parentheses call the default constructor. For our struct, that means "use the default values", so = {} and = false apply to the new block.

Each call to new makes one new node. The nodes do not disappear when a function returns, unlike a local variable. That is why a trie can grow across many function calls. In this lesson we never call delete, so the memory lives until the program ends. Lesson three shows how to remove nodes safely.

A local variable such as int x = 5; lives on the stack and vanishes when its function ends. The stack is a region of memory that grows when functions are called and shrinks when they return. A heap block from new is different. It stays until someone deletes it, which is why a trie built inside a function still exists after the function returns.

Insert: laying down one road at a time

Inserting a word means walking from the root and creating any missing road. Here is the idea in words. For each letter of the word, look at the current node's slot for that letter. If the slot is empty, create a new node and store its address there. Then move to that node and repeat. When the letters run out, you are at the node for the whole word. Set its flag.

Trace the insert of "car" into an empty trie. The root has all 26 slots null, so there are no words yet.

• Start. cur is the root. The first letter is c, index 2.
• Slot 2 of the root is null. Create a node, store its address in slot 2, and move cur to it.
• The next letter is a, index 0. Slot 0 of the c node is null. Create a node, store it, and move to it.
• The last letter is r, index 17. Slot 17 of the a node is null. Create a node, store it, and move to it.
• No letters remain. cur is the node for "car". Set isEnd to true.

The trie now has four nodes: the root, the c node, the a node and the r node. Now insert "card" into the same trie.

• Start at the root. Letter c. Slot 2 is not null, so move to it without creating anything.
• Letter a. Slot 0 of the c node is not null. Move.
• Letter r. Slot 17 of the a node is not null. Move.
• Letter d, index 3. Slot 3 of the r node is null. Create it and move to it.
• No letters remain. Set isEnd on the d node.

Only one new node was created. The letters c, a and r were shared. This is the core of the trie: the cost of a new word is only the part that is new. Inserting a word that shares a long prefix is cheap, and inserting a word with a brand-new beginning costs one node per letter.

The code for insert follows that loop exactly.

void insert(const string& w) {
    Node* cur = root;
    for (char c : w) {
        int i = c - 'a';
        if (!cur->next[i]) cur->next[i] = new Node();
        cur = cur->next[i];
    }
    cur->isEnd = true;
}

Look at the three important lines of the loop.

• int i = c - 'a'; turns a letter into a slot number. Characters in C++ are small integers. The character 'a' is 97 in the usual ASCII encoding and 'c' is 99, so 'c' - 'a' is 2. The arithmetic works only for lowercase letters. An uppercase 'C' is 67, so 'C' - 'a' is negative, and the program would reach memory before the array. The common mistakes section shows what happens.
• if (!cur->next[i]) cur->next[i] = new Node(); creates the road only when it is missing. The exclamation mark means "not", so !cur->next[i] is true when the pointer is null.
• cur = cur->next[i]; moves the walker one step down the road. After this line, cur is the child node for the letter.

After the loop, cur points at the node for the whole word, and setting isEnd marks it as a stored word. The main function you will read later calls insert once per word.

Search and startsWith: the same walk

Searching for a word and checking a prefix use the same walk. The walk is the loop from insert without the creation step. For each letter, move to the child. If a slot is null, the path is missing and the answer is "no".

The walk ends at some node, or at nothing. From that node we ask two different questions.

• For startsWith, the answer is simply "did we reach a node?". Any node means at least one stored word has these letters as its beginning, because every node exists only because some word passed through it when it was inserted.
• For search, we need more. We must reach the node, and that node's isEnd flag must be true, so a stored word ends exactly there.

Here is the walk as a function that returns the node, or nullptr when the path is missing.

Node* walk(const string& s) const {
    Node* cur = root;
    for (char c : s) {
        cur = cur->next[c - 'a'];
        if (!cur) return nullptr;
    }
    return cur;
}

Notice the early return nullptr. Once a slot is null there is no next node to read. Reading cur->next on a null pointer is undefined behaviour, which means the C++ standard allows anything to happen. In practice it usually ends in a crash with the message Segmentation fault (core dumped). The check inside the loop protects the program. The loop never reads from a null node, because the if returns before the next iteration.

Then the two public functions read the answer from the walk.

bool search(const string& w) const {
    Node* n = walk(w);
    return n && n->isEnd;
}
 
bool startsWith(const string& p) const { return walk(p) != nullptr; }

The n && n->isEnd check first asks whether n is non-null. If it is null, C++ stops there and never reads n->isEnd. The && operator uses short-circuit evaluation, which means it stops as soon as the answer is known. You will use this pattern in many tries, and the order matters. Writing n->isEnd && n would read a field from a null pointer first.

A worked trace: "ca" against car and card

After inserting car and card, the trie has the path c, a, r, with d hanging below r. Check two strings.

For search("ca"):

• The walk goes from the root to c, then from c to a. Both slots exist. walk returns the a node.
• The a node exists, so startsWith("ca") is true.
• The a node's isEnd flag is false, because no stored word is "ca". So search("ca") is false.

For search("cat") on the same trie:

• The walk goes root to c, then c to a, then a to t. The a node has no slot for t, so walk returns nullptr at that step.
• search returns false immediately, and startsWith("cat") is false too.

The difference between the two answers is the flag. A prefix node exists, but it is not a word. This single flag is the reason the structure can answer both questions with one walk.

A worked trace: a prefix with no node

Now check startsWith("cab"). The walk goes root to c, then c to a. Then it looks at slot 1, which stands for b. The a node has no child for b, because no stored word goes c, a, b. The walk returns null, so startsWith is false. The walk stopped after three steps, even though the trie holds several words. Its work depended on the length of "cab", not on how many words exist.

Worked example 1: the complete demo

The program below builds the three words car, card and care, then asks five questions. It is a complete program, so the Run button can execute it. You do not need to type anything for this one.

Output. The values are 1 for true and 0 for false, because cout prints a bool as a number by default:

1
0
1
0
0

Each line answers one question. The first is true because car was inserted. The second is false because "ca" is only a prefix. The third is true because at least one word starts with "ca". The fourth and fifth are false because no stored word starts with "cat" or "cab".

Why does a class appear here? The Trie class groups the root and the methods that act on it, so main does not need to pass a root pointer to each call. This is the style you will see in most C++ code. The notation t.insert("car") means "call the insert function that belongs to the object t". The earlier examples in this lesson use plain functions and a global root, which is simpler to read while you learn the walk. Both forms do the same work.

Read the public: line. It says the methods after it can be called from main. The root pointer is private by default in a class, so main cannot touch it directly. This protects the trie: callers can only use the methods you chose to expose.

Worked example 2: reading words from the keyboard

The next program reads a list of stored words, then a list of queries, from standard input. Standard input is what the program receives from the keyboard or from a file. The Input box in this course sends whatever you type there to the program as if you typed it on the keyboard.

Type this into the Input box. Put the values on separate lines or separate them with spaces; the program reads tokens, so both work:

4
car card care dog
5
car ca dog cat card

The first number, 4, is how many words to store. The next four tokens are the words. The 5 is the number of queries, followed by five query words. The program prints yes if a query is a stored word and no otherwise.

The output for that input is:

yes
no
yes
no
yes

Trace the queries. "car" is stored, so yes. "ca" is a prefix only, so no. "dog" is stored, so yes. "cat" was never inserted. The walk goes c, then a, then looks for t under a, which is missing, so the answer is no. "card" is stored, so yes.

Two details matter for real use. First, cin >> w reads a token, which is a run of characters without spaces. The program cannot store a phrase such as "ice cream" as one word, because the space ends the token. Second, search assumes every letter is lowercase. If you type Car, the expression 'C' - 'a' is negative and the program reads memory outside the array. The next example handles that case.

The cin >> n line reads the first number. The for loop then reads exactly that many words. Always read the count first. If you skip it, the program does not know where the words end, and a misplaced number will be read as a word.

Worked example 3: counting nodes

A trie's memory cost is the number of nodes. The next program counts them by visiting every node. The counting function calls itself on each child. A function that calls itself is called recursive. Each call handles one node and hands the children to new calls. Its base case is the null pointer, which counts as zero nodes, so the calls stop when they reach empty slots.

Type this as input:

3
car card care

Output:

nodes: 6

Trace the count. The root counts as 1. Its only child is c, which counts 1. The c node has child a, and a has child r. Those add 1 each. The r node has children d and e, so they add 2. Total: root 1, c 1, a 1, r 1, d 1, e 1, which makes 6. The root counts because it is a real node in memory, even though it stores no letter. When you reason about memory, count the root too.

Why does the loop run over n->next directly? A range-based for loop over an array visits each element in order. Here each element is a Node*, and countNodes accepts a null pointer, so empty slots contribute 0 and the code does not need an if inside the loop. This keeps the code short.

Now watch how the count grows as words are added. The next program prints the node count after each insert, so you can see the shared prefixes at work.

Type this as input:

6
to tea ted ten a i

Output:

after to: 3
after tea: 5
after ted: 6
after ten: 7
after a: 8
after i: 9

Trace the first two lines. Inserting "to" creates the root's t child and the t node's o child. The root plus two new nodes gives 3. Inserting "tea" reuses t, then creates e and a, adding two more nodes. The total is 5. Then "ted" reuses t and e, and adds only d, so 6. Then "ten" reuses t and e and adds n, so 7. The word "a" starts a new road from the root, so it adds one node, 8. The word "i" adds one more, 9.

The table below gives the same story in one place. The "new nodes" column is the number of nodes each insert created. The "shared" column shows letters that were already on a path.

The point to take from the table is that a word costs new nodes only for the letters past the shared prefix. A long word that shares a long beginning is cheap. Interviewers often ask for the worst case: a word with no shared letters costs one node per letter.

Worked example 4: validating input and reporting duplicates

Real programs receive messy input. The next example reads tokens, converts uppercase letters to lowercase, rejects anything that is not a letter, and reports whether each word was new. This version of insert returns a result, which is a useful pattern: a function that changes the trie can also report what happened.

Type this as input:

Car card CAR cat 42

Output:

added
added
exists
added
invalid

Trace the five tokens. "Car" has an uppercase letter. The loop lowercases it to "car", which is new, so it prints added. "card" is new. "CAR" lowercases to "car", which is already stored. The walk reaches the existing node, its flag is already true, and the function prints exists. "cat" is new. "42" contains digits, so isalpha is false and the function returns invalid before it touches the trie at all.

Notice the order of work in addWord. The validation loop runs first, and it builds the lowercase copy w. Only then does the walk start. This order means an invalid word never leaves half-built nodes behind. A bad input that created nodes before failing would leave junk in the trie, which is a bug that is hard to find later.

The static_cast<unsigned char> in the isalpha and tolower calls is a rule you should follow. The functions in <cctype> expect a value that fits in an unsigned char. A plain char with a negative value, which can happen with non-ASCII bytes, is undefined behaviour when passed directly. The cast avoids it. The cast back to char after tolower is needed because tolower returns an int.

The while (cin >> token) loop reads tokens until the input ends. When there is no more input, cin >> token becomes false and the loop stops. This is the standard way to read an unknown amount of input in C++.

What happens inside memory

Everything in the trie lives on the heap, but the names live elsewhere. This distinction is where many beginners get confused, so trace it once with care.

When the program starts, the global variable root exists for the whole run. It holds one address: the address of the root node. The root node lives on the heap. It contains 26 pointers and a flag. Each pointer holds either null or the address of another heap node.

Inside insert, the local variable cur is a pointer that lives only while insert runs. It starts with the same address as root. Each loop step copies a different address into cur. When the function returns, cur disappears from the stack, but the nodes it touched remain on the heap, because they were created with new. That is why the trie survives after insert ends.

A picture helps. Think of the nodes as boxes on a shelf in a warehouse, which is the heap. Each box has 26 small labelled tags, and each tag holds the address of another box, or nothing. The global root is a note that says "start at box 4721". The local cur is a sticky note you move from box to box while you walk. When you finish, the sticky note is thrown away, but the boxes stay on the shelf.

Here is the memory after inserting "car" and then "card", written as a list of nodes:

• Node A, the root. Its slot for c holds the address of node B.
• Node B, for "c". Its slot for a holds the address of node C.
• Node C, for "ca". Its slot for r holds the address of node D.
• Node D, for "car". Its flag isEnd is true. Its slot for d holds the address of node E.
• Node E, for "card". Its flag isEnd is true. All of its slots are null.

Two words share three nodes, A, B and C, plus D in the path. The cost of "card" is one new node, E, plus its flag. Each address stored in a slot is 8 bytes on a 64-bit system, so a new road costs one slot in the parent node, which was already allocated.

Now compare the trie with a hash set. A hash set stores the whole word once, in a bucket. For 100,000 words of about eight letters, a hash set holds roughly one string object per word, plus a little overhead. A trie stores up to one node per letter in the worst case, and each node is about 216 bytes. Without shared prefixes, that is 800,000 nodes times 216 bytes, about 173 MB. Real dictionaries share a lot of prefixes, so the true count is far lower, but the trie still costs more memory per word than a hash set. Lesson four returns to this number with a fair comparison.

Look also at the ownership. Nothing in this lesson frees a node, so memory is reclaimed only when the program exits. For a short program that is fine. For a server that runs for weeks, unfreed nodes are a leak, a growing amount of memory that is never used again. Lesson three shows how to delete nodes safely.

Complexity

Let L be the length of the word you insert or search.

• Insert: O(L) time. One step per letter, plus at most one allocation per letter. The number of words already stored does not change the work for one word.
• Search: O(L) time. One step per letter, plus a constant check of the flag.
• startsWith: O(L) time, the same walk without the flag check.
• Space: each insert creates at most L new nodes, so the total is O(total letters inserted) nodes. Each node holds 26 pointers, so the constant factor is large.

Compare with the alternatives. A hash set checks a word in O(L) average time, but it cannot answer prefix questions without scanning. A sorted array answers a prefix in O(log n + L) with binary search, but each insert costs O(n) because items move. The trie's cost for one word does not depend on how many words are stored, and that is the main reason to choose it.

Common mistakes and the messages they produce

Each mistake below is one a beginner makes. Each has a symptom you can recognise, and the messages shown are real output from the compiler or the sanitizer.

Mistake 1: forgetting the word-end flag

If search returns true for "ca" after you inserted "car", the flag is set in the wrong place. Check that insert sets cur->isEnd = true after the loop, not inside it. Setting it inside the loop marks every prefix as a word, which is the bug. Each prefix of "car" would then answer yes to search.

Mistake 2: leaving the array uninitialised

Writing Node* next[26]; without = {} leaves garbage. A program may appear to work in one run and crash in another, because the garbage depends on what memory held before. Compile with warnings turned on and run with the address sanitizer. For a single file, the command looks like this:

g++ -std=c++17 -Wall -Wextra -g -fsanitize=address -o trie trie.cpp

The sanitizer reports bad memory access with a line such as ERROR: AddressSanitizer: SEGV on unknown address. It also prints a stack trace, a list of the calls that led to the bad line. The top line of the trace names the function and the file line. That is where to look first.

Mistake 3: an out-of-range letter

If the input contains an uppercase letter, a digit or a space, c - 'a' falls outside 0 to 25. C++ does not check array bounds, so the program reads or writes memory it does not own. Sometimes it prints a wrong answer. Sometimes it crashes. The sanitizer output for an uppercase letter on the program root->next[w[0] - 'a'] = ... with w equal to "C" looks like this in a real run:

ERROR: AddressSanitizer: SEGV on unknown address 0x7227f1ddff50
The signal is caused by a WRITE memory access.

The index for 'C' is -30, so the write goes before the start of the array. The fix is to validate or convert input before the walk, as in worked example 4.

Mistake 4: dereferencing a null pointer

If walk does not return early when a slot is null, the next loop iteration reads cur->next through a null pointer. Here is the sanitizer output for a short program that walks "ab" through an empty trie with no check:

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008
The signal is caused by a READ memory access.
Hint: address points to the zero page.

The hint is useful. An address close to zero means a pointer was null, and the offset read from it was small. Without the sanitizer the same bug appears as Segmentation fault (core dumped) with no line number. Build with -g so the sanitizer can name the line.

Mistake 5: a missing include or a missing namespace

If you use string without #include <string> and without writing std::string, g++ stops with an error. The first line of the real output for a file that says string s = "x"; with no include is:

error: 'string' was not declared in this scope

The fix is to add #include <string> at the top, and either add using namespace std; or write std::string. Both styles are correct, and this course uses the using line so the code stays short.

Mistake 6: using the type before it is declared

If you write a function that takes a Node* above the struct Node definition, the compiler cannot find the name yet. With g++, the first error line for an unknown name reads like this. The name Thing was never declared in the test that produced this line:

error: 'Thing' was not declared in this scope

A Node used above its struct gives the same kind of message, with Node in place of Thing.

The fix is to move the struct above the code that uses it. This is a compile error, so the program never runs. Read the first error line and ignore the long list of follow-up messages. The compiler often reports the same root cause several times.

Debugging walkthrough: why does search return false?

Suppose you insert "apple" and "apply", and then search("apply") returns false. The order below works for almost every trie bug. Work through it in sequence instead of guessing.

Step 1: confirm the input. Print the word you inserted and the word you searched, with brackets around them. Trailing spaces and capital letters are invisible otherwise. Add cout << "[" << w << "]\n"; inside insert. If the output shows [apply ], the bug is the input, not the trie. Input from the keyboard often has a trailing space or a carriage return that the terminal does not show.

Step 2: walk the path by hand. Write the letters of "apply" on paper with their slot numbers: a is 0, p is 15, p is 15, l is 11, y is 24. Then compare them with the nodes you created during insert. A print that shows each index as the loop runs tells you exactly where the walk leaves the stored path.

Step 3: find the first missing slot. Add a print inside walk that shows the letter and whether the slot is null. The first null slot tells you where the stored path and the search path disagree. Suppose the stored path ended at "appl" because the insert loop stopped one letter early. Then the search would find a null slot at the letter y, and the print would show exactly that.

Step 4: check the flag. Print cur->isEnd at the end of the walk. If the walk reached the right node and the flag is false, the insert never set it on that node. If the flag is true and the answer is still wrong, the search reads a different node than you think.

A debugger does the same work without edits. Running the program under gdb with a breakpoint on the search line, then printing cur->next[24], lets you check each step. Use whichever tool you prefer. The principle is the same: find the first place where the stored data and the expected data disagree.

Keep one habit from this walkthrough. A trie bug almost always shows up as a missing node or a missing flag. You can verify both with the node count from worked example 3. If the count after an insert is not the number you expected from the table, the insert created the wrong nodes.

Variations and edge cases

Edge cases are where interviewers test whether you understand the structure. Work through these with the code in front of you, and check each one by running it.

• The empty word. insert("") loops zero times, so cur is still the root. The code then sets root->isEnd = true. After that, search("") returns true. Whether that is correct depends on the task. Many problems forbid empty strings, so say so in your answer and handle it on purpose.
• The empty prefix. startsWith("") returns the root, which is not null, so it returns true even when the trie is empty. Ask what the caller expects. Some problems treat the empty prefix as "any word exists".
• A repeated insert. Inserting "car" twice changes nothing after the first time. The walk finds every node already there and sets the flag again. The result is the same, though the work is the same too.
• A word that is a prefix of another. Inserting "car" after "card" only sets the flag on the existing node for "car". No new nodes are created. This is the case the flag exists for.
• A very long word. The walk time grows with the word length. A 1,000 letter word costs about 1,000 steps, and its memory cost is up to 1,000 new nodes if none of its prefixes exist.
• Mixed case and symbols. The code above rejects them when you call addWord. You may choose to lowercase input first, but then decide what happens to digits.
• A word that is a prefix of nothing else. Its last node has no children. A leaf node ends a word, so its flag must be true. If you ever find a leaf with a false flag, something went wrong during insert or delete.

Each of these is a line you can test. Writing the test first, then the code, catches these errors before an interviewer does. Lesson three will add the delete case, which has the most traps.

Practice

Each exercise builds on the code above. Try to solve each one before you open the solution. Some exercises ask you to predict a result first. Write your prediction down before you run the program.

1. Insert the words "to", "tea", "ted" and "ten" into a trie. Predict the result of search("te") and startsWith("te"), then check your answer with the program.

2. Add a method bool isEmpty() const to the Trie class that returns true when no word has been inserted.

bool isEmpty() const {
    for (Node* child : root->next) {
        if (child) return false;
    }
    return true;
}

3. Write a function int countWords(Node* n) that returns how many words end at or below node n, using recursion.

int countWords(Node* n) {
    if (!n) return 0;
    int total = n->isEnd ? 1 : 0;
    for (Node* child : n->next) total += countWords(child);
    return total;
}

4. Explain in one sentence why startsWith("ca") can be true while search("ca") is false.

5. Change insert so it returns true when the word was new and false when it already existed. Test it with the input car car card and expect true, false, true.

bool insert(const string& w) {
    Node* cur = root;
    for (char c : w) {
        int i = c - 'a';
        if (!cur->next[i]) cur->next[i] = new Node();
        cur = cur->next[i];
    }
    if (cur->isEnd) return false;
    cur->isEnd = true;
    return true;
}

6. Predict the node count, with the root included, after inserting "a", "ab" and "abc" into an empty trie. Then run worked example 3 with that input to check.

7. Write a program that reads words and counts how many of them start with each letter. Use an array of 26 integers instead of a trie. Hint: the index for the first letter is w[0] - 'a'.

8. What does search("") return after insert("car") only? Explain your answer using the code.

9. A teammate writes Node* next[26]; inside a struct with no initialiser and calls new Node(). Explain what can go wrong, and how you would detect it.

10. Suppose the alphabet were 'a' to 'z' plus the digits 0 to 9. What would you change in the node, and what is the new child count?

What you now know

• A trie stores words as paths of letters, so words that share a beginning share their first nodes.
• Each node holds a child array of pointers and a flag that marks a word end.
• Insert, search and startsWith each walk one step per letter, so they cost O(L) time, where L is the word length.
• You must initialise the child array, validate the input letters, return early on a null pointer, and set the word-end flag only at the end of the word.
• Memory use is the price: each node holds 26 pointers, so tries cost more memory per word than a hash set.

The next lesson uses the same walk to list every stored word that starts with a prefix, in alphabetical order.