Here's a puzzle that trips up almost everyone the first time.

You built a trie with six words: apple, app, ape, apex, bat, and bath. Now someone calls search("ap").

Think about what happens. You start at the root. Follow a — found it. Follow p — found it. Every node on that path is real. The traversal never hits a dead end. You successfully walked the entire query string without a single miss.

So does search("ap") return true?

Your instinct says yes. The path is there. The characters match. What more could you need? But pause for a moment — did anyone ever insert the string "ap" as a word? It's a prefix of apple and app and ape, sure. But being a prefix of real words and being a real word are very different things.

This is the trie's version of a ghost: a path that exists structurally but was never claimed as a complete word. And if your search function can't tell the difference, it will report phantom words that nobody ever stored.

Every trie node has exactly two fields. Tap each one below to see what it does — one of them is the ghost-buster.

class TrieNode {

  children: Map<string, TrieNode>

  isEnd: boolean

  constructor() {

    this.children = new Map()

    this.isEnd = false

  }

}

Below is the trie you built with those six words. Several queries are about to come in — some searching for real words, some searching for ghosts. For each one, the path will light up as you trace it through the tree.

Here's what should bother you: the traversal logic alone cannot distinguish real words from phantoms. When you walk the trie for "ap", every step succeeds — a exists, p exists under a, and you never hit a dead end. The traversal is happy. It found everything it was looking for. Yet "ap" was never inserted. So if the traversal succeeds in both cases, there must be something other than the walk itself that separates a word from a prefix-that-happens-to-exist.

Before each answer is revealed, commit to your prediction. The first couple might feel like coin flips. But by the third or fourth query, a visual pattern will emerge — something about the nodes at the end of successful paths. Some of them carry a mark that others don't. Once you see what that mark is and when it gets placed, the distinction between search and startsWith will feel almost trivial.

Pay attention not just to whether the path exists, but to what's on the node where the path ends. That's where the answer lives.

So what separates a real word from a ghost? A single boolean: isEnd.

When you insert "apple", you create (or traverse) five nodes: a → p → p → l → e. But only the last node — e — gets marked with isEnd = true. The four intermediate nodes are structural scaffolding. They exist to support the path, not to claim that "a", "ap", "app", or "appl" are words.

This is why "ap" felt like a ghost. The node for p (after a) exists — it has to, because apple, app, ape, and apex all pass through it. But nobody ever inserted "ap" as a complete word, so its isEnd flag is false.

Here's the elegant consequence: search and startsWith share nearly identical code. Both walk the trie character by character. Both return false if a child is missing. The only difference is the last line. search returns node.isEnd — is this a real word? startsWith returns true — does the path exist at all?

That means the “bug” you might write in search (forgetting to check isEnd and just returning true after the walk) is literally the correct implementation of startsWith. Two functions, one flag, zero extra logic. The trie makes the distinction almost free.

Test your understanding: if you insert "app" and "apple", which nodes on the path a → p → p → l → e have isEnd = true? Tap the ones you think are terminal, then check.