Everything you've done so far in the trie has been deterministic. At every node, you knew exactly which child to follow — the one matching the next character. One character, one child, no choices. That's why search and startsWith are both O(L): you never backtrack, never explore alternatives, never wonder “what if I'd gone left instead?”

Now break that assumption.

What if the pattern is b.d? That . is a wildcard — it matches any single character. When you reach the node for b and need to follow ., there's no single child to pick. The b node might have children for a, e, i, o, u, and a dozen other letters. The wildcard says “all of them could work.”

Suddenly you're not walking a path. You're exploring a maze. Each wildcard multiplies your search by the number of children at that level — potentially up to 26 for English lowercase letters. And if there are two wildcards in a row? The multiplication compounds.

This is the moment where a trie search transforms from simple traversal into DFS with backtracking. And it's why LC 211 — “Design Add and Search Words Data Structure” — is a medium-difficulty problem despite the trie itself being straightforward. The trie isn't the hard part. The wildcard is.

Watch the pattern a.p in action. The wildcard fans out to every child — then the literal p prunes the dead ends right back.

Time to feel the branching explosion firsthand. Below is a trie with several words inserted. You'll run wildcard queries against it — starting with a single ., then escalating to patterns with multiple wildcards.

Here's the mental shift: up until now, every trie traversal you've done was a straight walk. One character, one child, no choices. Now, every . in the pattern is a fork in the road. The search has to try all children at that node, not just one. And each of those children might have its own subtree that needs exploring. If two wildcards appear in sequence, the branching multiplies — the first . might fan out to five children, and the second . fans each of those out again.

But the explosion isn't as bad as it sounds, and that's the non-obvious part. The concrete (non-wildcard) characters in the pattern act as pruning constraints. A pattern like b.d forks at the ., sure — but at the very next level, only branches that have a d-child survive. Everything else is a dead end that gets killed immediately. The wildcards create breadth, but the literal characters collapse it right back down.

Your job is to predict how many branches get explored before seeing the answer. Count the forks, but also count the prunes. The ratio between the two is what separates “exponential blowup” from “manageable search.” That ratio is also the reason the trie-based approach beats brute force: a HashSet can't prune anything — it has to check every stored word against the full pattern.

You just felt the difference between O(L) deterministic traversal and DFS with backtracking. A single wildcard at one position can explore up to 26 children. Two wildcards in a row? Up to 676 paths. The branching factor multiplies at every wildcard position.

The recursive implementation mirrors exactly what you did. For each character in the pattern:

• If it's a normal letter, follow that one child (or return false if it doesn't exist)
• If it's ., loop over every child of the current node and recurse on the remaining pattern

If any recursive branch returns true, the entire search returns true. This is textbook DFS with backtracking — the same pattern you use in maze solving, N-queens, and Sudoku. The trie just gives the recursion a natural tree structure to explore.

So why is this better than brute force? A HashSet with wildcard matching would need to check every stored word against the pattern — that's O(N * L) where N is the number of words. The trie prunes entire branches. If you search b.d and the trie has no children starting with b, the search ends immediately. Even when it does branch at the wildcard, the non-wildcard characters kill dead-end paths fast.

This is why LC 211 is classified as a trie problem. A hash set can do exact match in O(1), but the moment you introduce a single ., it falls apart. The trie sacrifices constant-time exact lookup for something a hash set can never offer: structural pruning of partial matches.

Step through the recursive implementation below. Notice how the wildcard branch (lines 5-7) is the only addition to regular search — everything else is identical.

function search(node: TrieNode, word: string, i: number): boolean {

  if (i === word.length) return node.isEnd

  const ch = word[i]

  if (ch === '.') {

    // Wildcard: try EVERY child

    for (const child of node.children.values()) {

      if (search(child, word, i + 1)) return true

    }

    return false

  }

  // Literal: follow one child

  const next = node.children.get(ch)

  if (!next) return false

  return search(next, word, i + 1)

}