Trie Insert, Search, and StartsWith Explained: Tracing Apple & App

Imagine you are building a real-time autocomplete engine. Your users type ap, and you need to instantly know whether apple, apply, and app exist in your dictionary, or if any valid word begins with those letters. If you store your dictionary in a standard hash set or list, checking whether app is a valid prefix requires scanning through every single string starting with a. As your dataset grows to millions of entries, prefix-based filtering becomes too slow for smooth user interaction.

Our working example focuses on this exact challenge. Given an initially empty trie, we want to perform a series of operations: insert("apple"), test queries like search("app") versus startsWith("app"), insert app explicitly, and check how exact word matching differs from prefix matching. Without a specialized data structure, distinguishing between an exact word boundary like app and an internal prefix like ap requires complex substring indexing.

Prefix trees, or tries, solve this by sharing common character paths. Instead of treating words as monolithic strings, a trie breaks them down node by node, turning prefix checks into direct traversals.

To understand how our locked working example (apple and app) operates, we need to look under the hood of a Trie (pronounced "try", derived from "retrieval"). Unlike a flat hash map that stores a string as a single opaque key, a Trie decomposes strings into individual characters and lays them out as a directed tree.

Each node in this tree represents a single character and contains two primary components:

- A boolean flag, typically called isEnd, which marks whether the path from the root down to this node spells a complete inserted word.

Root
└── a
└── p
└── p *
└── l
└── e *

In our working example, inserting apple and app builds a shared branch for a $\to$ p $\to$ p. Because we explicitly call insert("app"), the second p node sets its isEnd flag to true (marked by the * above). When we subsequently insert apple, the traversal reuses the existing a-p-p path, appends l and e, and sets isEnd to true on the final e node.

This structural separation between prefix traversal and word completion explains why exact-word search and prefix search behave differently. A search for the whole word app checks if we land on a node where isEnd == true. A startsWith check for ap only cares if the path exists, ignoring the isEnd flag entirely.

To see how the prefix tree architecture comes alive, let us trace the locked working example: inserting apple and app, followed by queries for whole words (search) and prefixes (startsWith). Maintaining intermediate states will reveal why search and startsWith behave differently.

Given

An empty trie root node with children mapping and isEnd = false. We execute these operations in order:
1. insert("apple")
2. search("app")
3. startsWith("app")
4. search("apple")
5. insert("app")
6. search("app")
7. search("ap")

Step 1: insert("apple")
- Start at the root. Character a is missing, so create a new node for a. Move to a.
- Character p is missing, create node p. Move to p.
- Character p is missing, create node p. Move to p.
- Character l is missing, create node l. Move to l.
- Character e is missing, create node e. Move to e.
- Mark this final e node with isEnd = true.

Step 2: search("app")
- Traverse root -> a -> p -> p. All nodes exist.
- Check isEnd at the second p node. It is false because we only inserted apple, not app.
- Result: false.

Step 3: startsWith("app")
- Traverse root -> a -> p -> p. All nodes exist.
- We do not check isEnd for prefix queries. Since the traversal succeeded without hitting a missing child pointer, the prefix exists.
- Result: true.

Step 4: search("apple")
- Traverse root -> a -> p -> p -> l -> e.
- Check isEnd at the final e node. It is true.
- Result: true.

Step 5: insert("app")
- Traverse root -> a -> p -> p. The nodes already exist, so no new allocations occur.
- Set isEnd = true on this second p node.

Step 6: search("app")
- Traverse root -> a -> p -> p.
- Check isEnd at this node. It is now true.
- Result: true.

Step 7: search("ap")
- Traverse root -> a -> p. Both nodes exist.
- Check isEnd at the p node. It is false (only app and apple marked their ends further down or at this exact spot, but the root-to-p path specifically ended at isEnd = false initially before app was inserted? Wait: the second p is isEnd = true, but the first p is isEnd = false).
- Result: false.

Result

By tracking whether a node represents a valid word boundary (isEnd), the trie distinguishes between a complete stored word (search) and an intermediate path (startsWith).

Try this: Trace what happens to the isEnd flags at each node when insert("app") is called immediately after insert("apple"). Which node's isEnd flag changes state?

Now that you have seen how inserting apple and then app builds out the prefix tree and toggles terminal flags, it is time to test your mental model. Consider our locked working example: the trie currently contains the words apple and app. Both words share the exact same starting prefix a -> p -> p.

Recall the crucial distinction established in the previous steps: search(word) requires the final character node to have its isEnd flag set to true, whereas startsWith(prefix) only requires that the path of characters exists in the tree, regardless of whether any node along that path marks the end of a complete word.

Take a moment to trace through the pointer movements for the operation search("app"). Look closely at where the traversal ends and inspect the isEnd boolean state of that final p node before you jump to a conclusion.

Answer the following question based on the locked working example after both apple and app have been successfully inserted into the trie.

Now that you have traced how insert, search, and startsWith operate on our locked working example of apple and app, let us look at how this exact structure scales to a related challenge: adding wildcard character support, similar to a regular expression . that matches any single letter.

Recall our trie structure from the previous steps. When searching for ap.le, the dot character cannot simply be matched by checking node.children['.']. Instead, because a wildcard matches any single character, the traversal must branch out to all non-null children of the current node.

To see how this works, consider our trie containing apple and app. If we query ap.le, the walk proceeds through root $\to$ a $\to$ p. At the dot . position, instead of following a single child edge, the algorithm iterates over every existing child in node.children (which includes p for app and p for apple), spawning parallel recursive searches for the remaining suffix le.

This demonstrates the power of the trie architecture: operations that seem expensive on flat hash tables become systematic path-exploration problems in a tree.

Question

Suppose a trie contains the words bat, cat, and rat. You are asked to implement a wildcard search function searchWithWildcard(word) where a dot . matches any single character. Explain how your algorithm should behave at the node level when it encounters . while searching for b.t versus ..t, and state whether each query returns true or false.