Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Tries

Medium6 min readdsatries

Introduction to Tries

The last two sections built trees that organize data by comparison - a binary search tree decides "go left or right" by comparing whole values, which makes it perfect for ordered numeric data and "what's near this value?" queries. This section turns to a fundamentally different organizing principle. A trie (pronounced "try," from retrieval) branches not on a comparison but on the characters of a string, one level per character, so that words sharing a prefix share a path from the root. Where a BST answers "what's near this value?", a trie answers "what shares this prefix?" - and that single shift makes it the structure behind autocomplete, spell-checkers, IP routing tables, and word-search puzzles.

This is the introduction to the section. It defines the trie structure, explains the prefix-sharing insight that makes it efficient, fixes the canonical node representation used throughout the section, and frames the recurring trade-offs - time, space, and when a trie beats a hash set.

The Core Idea: Prefix Sharing

Imagine storing the words cat, car, card, and dog. A hash set stores each as an independent blob of characters. A trie instead lays them out as paths:

graph TD
    Root(( )) --> C((c))
    Root --> D((d))
    C --> A((a))
    A --> T((t ✓))
    A --> R((r ✓))
    R --> D2((d ✓))
    D --> O((o))
    O --> G((g ✓))

    style Root fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style T fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style R fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style O fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This diagram shows a trie holding cat, car, card, and dog. From the root, the letter c leads to a, which branches to t and r; r continues to d. The letter d leads through o to g. Nodes marking the end of a word are highlighted in green.

The words cat, car, and card all begin with ca, so they share the same first two edges; only where they differ does the path branch. A green node marks "a word ends here" - note that car ends at the r node and card continues past it, so a node can be both the end of one word and an interior node of a longer one. That single picture captures everything: a trie is a tree where each edge is labeled with a character, each node represents the prefix spelled by the path from the root to it, and a boolean flag marks which prefixes are complete words.

Why This Is Efficient

Searching for a word of length L in a trie takes O(L) time - you walk one edge per character, regardless of how many words the trie holds. Compare that to scanning a list of n words (O(n·L)) or even a hash set, which must hash the entire word (O(L)) and handle collisions. The trie matches the hash set on full-word lookup but wins decisively on the operation a hash set cannot do at all: prefix queries.

Asking "how many stored words start with ca?" or "give me every word beginning with ca" is a single O(prefix length) walk to the ca node in a trie, followed by exploring its subtree. A hash set has no notion of "starts with" - it would have to examine every key. This is the trie's reason for existing, exactly analogous to how the BST's reason for existing was order queries that a hash set couldn't answer.

Operation	Hash Set	Trie
Insert word (length L)	O(L)	O(L)
Search exact word	O(L)	O(L)
Starts-with prefix query	O(n·L) (scan all)	O(prefix length)
List all words with prefix	O(n·L)	O(prefix + matches)
Order by prefix / lexicographic	not supported	natural (sorted children)

Important: The decision rule mirrors the BST one. If you only need whole-word membership, a hash set is simpler and has less overhead. The moment you need prefix operations - autocomplete, "does any stored word prefix this string?", longest-common-prefix, prefix counting - reach for a trie. Prefix sharing is the one job a trie does that nothing else does as well.

The Canonical Trie Node

Throughout this section, a trie node has two parts: an array (or map) of child pointers indexed by character, and a boolean marking whether a word ends at this node. For lowercase-English problems we use a fixed 26-slot array, which gives O(1) child access:

class TrieNode {
    TrieNode[] children = new TrieNode[26];   // children[c - 'a']
    boolean isEnd = false;                      // true if a word ends here
}

The root is an empty TrieNode representing the empty prefix. To follow character ch, you index children[ch - 'a']. When the alphabet is large or unknown (Unicode, arbitrary symbols), swap the array for a HashMap<Character, TrieNode> - same logic, O(1) expected access, less wasted space. We note which representation a problem calls for as we go; the 26-array is the default unless stated otherwise.

Note: The isEnd flag is what distinguishes a word from a mere prefix. Both car and card create a path through the r node, but only if isEnd is true at r is car actually a stored word. Forgetting this flag is the single most common trie bug - you end up treating every prefix as a word, so a search for ca wrongly succeeds even though only cat, car, and card were inserted.

The Two Operations Everything Builds On

Every trie problem decomposes into two primitives, both simple walks:

Insert a word: start at the root; for each character, if the corresponding child doesn't exist, create it; descend into it. After the last character, set isEnd = true.

Search a prefix or word: start at the root; for each character, if the child doesn't exist, the prefix is absent - stop. If you consume all characters, you've reached the node for that prefix; whether it counts as a word depends on its isEnd flag, while for a prefix query merely reaching the node suffices.

graph TD
    A["insert / search: start at root, node = root"] --> B["for each char ch in string"]
    B --> C{"node.children[ch] exists?"}
    C -->|"No (insert)"| D["create child"]
    C -->|"No (search)"| E["return absent"]
    C -->|Yes| F["node = node.children[ch]"]
    D --> F
    F --> B
    B --> G["end: insert sets isEnd=true; search checks isEnd (word) or just arrival (prefix)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the two trie primitives. Both walk character by character from the root; insert creates missing children and marks the end as a word, while search returns absent on a missing child or checks the end flag on arrival.

Space, and the Honest Trade-offs

A trie's speed isn't free. Each node may carry a 26-pointer array even if it uses only one child, so a trie can consume far more memory than a hash set, especially for sparse data with little prefix overlap. The space is O(total characters across all words) in the best case (heavy sharing) but the constant factor from the fixed arrays is large. When memory matters, the hashmap-child variant or compressed tries (radix trees, which merge single-child chains) reduce the overhead - but those optimizations come later; the array-backed trie is the right default for learning and for the constrained-alphabet problems in this section.

Tip: When you see a problem mentioning prefix, starts with, autocomplete / suggestions, dictionary of words to match against, longest common prefix, or word search on a board, a trie is very likely the intended structure. The keyword "prefix" is the strongest tell, just as "order" or "range" signaled a BST.

What This Section Covers

The section builds outward from the structure to its hardest applications:

Implementation - building the trie class with insert, search, and startsWith from scratch (the foundation for everything else).
Prefix & search - wildcard matching, autocomplete suggestion systems, and finding the longest word buildable one character at a time.
String operations - replacing words by their shortest root, removing redundant sub-folders, longest common prefix, and edit-distance-bounded matching.
Trie + bit operations - a binary trie over the bits of integers to maximize XOR, showing the trie idea applies beyond letters.
Hard trie - the showcase problems: backtracking word search on a grid, streaming suffix matching, decomposing concatenated words, building word squares, and pairing words into palindromes.

Throughout, the recurse-and-branch instincts from the tree sections carry over directly - but the branching factor changes from two (left/right) to one-per-alphabet-symbol, and the organizing question shifts from ordering to prefix sharing. That shift is the whole point of the trie.

The next topic, Implement Trie (Prefix Tree), builds the data structure itself: a Trie class supporting insert, search (exact word), and startsWith (prefix test). It turns the two primitives sketched above into working code and establishes the node representation, the insert-creates-missing-children pattern, and the crucial isEnd distinction between a complete word and a mere prefix - the foundation every subsequent problem in the section relies on.

Back to DSA Mastery - Interview Prep, End to End