Trie Design

What is this?

A trie is a filing cabinet where the drawers are letters. To file card you open drawer c, then a, then r, then d, and mark that last drawer "a word ends here". Everything beginning car shares the first three drawers, which is why the structure is compact and why asking "is there anything filed under car?" takes three steps regardless of how many words exist.

This chapter builds that, then stretches it twice: once by allowing a wildcard in the query, and once by noticing that the drawers do not have to be letters.

💡 Fun fact: Design In-Memory File System is a trie in disguise, and seeing that collapses it from a fiddly design problem into about twenty lines. A path is a list of components, a directory is a node whose children are its entries, and a file is a node carrying content instead of children. ls then becomes "return this node's children, sorted" — and because the sorting requirement is stated in the problem, using an ordered map or sorting on read is a deliberate choice worth mentioning.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: a node holds a map from label to child plus a flag saying whether a key ends here. Exact lookup follows one label per step; a wildcard follows all of them; and the labels can be any unit you like.

1. The structure

class Node:
    def __init__(self):
        self.children = {}      # label -> Node
        self.is_end = False     # a complete key finishes here

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, Node())
    node.is_end = True

is_end is not optional. Without it a trie containing card would report car as present, because the path exists — the flag is what distinguishes "a key ends here" from "a key passes through here".

2. Wildcards mean branching

def search(node, word, i):
    if i == len(word):
        return node.is_end
    ch = word[i]
    if ch == '.':
        return any(search(child, word, i + 1) for child in node.children.values())
    return ch in node.children and search(node.children[ch], word, i + 1)

A concrete character narrows to one child; a . must try them all. That is why the cost is O(26^d · L) for d wildcards — each dot multiplies the branching. A query of all dots inspects the entire trie, which is worth stating when the interviewer asks about complexity.

3. The labels need not be characters

For a filesystem, split the path and use the components:

def resolve(root, path):
    node = root
    for part in path.split('/'):
        if part:                                   # skip the empty leading segment
            node = node.children.setdefault(part, Node())
    return node

mkdir is resolve and stop. addContentToFile is resolve then append to that node's content. ls is: resolve, and if the node is a file return its own name, otherwise return its children's names sorted. The whole API is three lines of trie walking plus that one branch.

4. A 30-second worked example

Insert cat, car, card; then query c.r:

root
 └── c
      └── a
           ├── t (is_end)          ← "cat"
           └── r (is_end)          ← "car"
                └── d (is_end)     ← "card"

search "c.r":
  'c' → one child, descend
  '.' → try EVERY child of node 'c' → only 'a' → descend
  'r' → 'a' has children {t, r} → 'r' exists → is_end? yes → True ✓

Three words, six nodes — the shared prefix ca is stored once. And note search("ca") returns False despite that path existing, because no key ends there.

5. Where you'll actually meet this

• Autocomplete. Each keystroke descends one node; the subtree below is the candidate set.
• Spell-check with wildcards. Matching patterns with unknown characters is the . branch.
• Filesystems and object stores. Path hierarchies, and prefix-based listing APIs.
• Configuration and routing tables. Hierarchical keys where the longest matching prefix wins.
• Contact and command lookup. Any interface where partial input must narrow a set of options live.

6. Problems in this chapter

▶ Add and Search Word (Wildcard)

Support adding words and searching with . matching any single character. Exact characters descend; wildcards branch to every child.
Pattern: trie with DFS on wildcards. Target: O(L) add, O(26^d · L) search.

▶ Design In-Memory File System

Implement ls, mkdir, addContentToFile and readContentFromFile. A trie over path components, where files carry content and directories carry children.
Pattern: trie with non-character labels. Target: O(path length) per operation, plus sorting for ls.

7. Common pitfalls 🚫

• Omitting is_end. Every prefix of a stored word would report as present.
• Treating a wildcard as a single wrong guess. It must try every child, which means recursion rather than iteration.
• Not handling the empty path segment. Splitting "/a/b" yields a leading empty string that must be skipped.
• Returning unsorted ls output. The problem requires lexicographic order; decide whether to sort on write or on read.
• Confusing a file with a directory. ls on a file returns the file's own name, not its (nonexistent) children.
• A 26-slot array for path components. Fine for lowercase letters, useless for arbitrary names — use a dictionary.
• Recursing per character on a very long word. Deep tries can exhaust the stack; iterate for exact search and recurse only for wildcards.

8. Key takeaways

1. A node is children plus an end-flag. The flag is what makes membership different from prefix existence.
2. Exact search narrows; wildcards branch. That difference is the whole cost model.
3. Labels can be anything — characters, path components, bits.
4. A filesystem is a trie, and recognising that turns a design question into a walk.
5. Sorted listing is a stated requirement, so choose where to pay for it.
6. Dictionaries beat fixed arrays for anything but a small known alphabet.
7. Why interviewers like it: the structure takes five minutes, leaving the whole interview for the extensions — wildcards, deletion, sorted listing, memory trade-offs.

Order: Add and Search Word (Wildcard) → Design In-Memory File System.