Tries (Prefix Trees)

Tries (Prefix Trees)

Why This Matters

A trie (pronounced "try") is a tree-like data structure optimized for storing and searching strings. Unlike hash tables or binary search trees, tries excel at prefix-based operations. Each node represents a character, and paths from root to leaf spell out words.

This matters because tries solve problems that other data structures struggle with. Need to find all words starting with "pre"? A hash table requires checking every word. A trie can do this in O(m) time where m is the prefix length, regardless of dictionary size. This makes tries perfect for autocomplete, spell checkers, IP routing tables, and dictionary problems.

In interviews, trie problems test whether you can recognize when prefix matching is the core requirement. Many engineers reach for hash tables or arrays, but tries provide better time complexity for prefix queries. Real-world systems use tries extensively: search engines use them for query suggestions, routers use them for longest prefix matching, and text editors use them for code completion.

What Engineers Usually Get Wrong

Most engineers think "tries are just trees with characters." While true structurally, the real power comes from how tries organize data by prefixes. Engineers often implement tries without considering space optimization—a basic trie can use significant memory, especially with large character sets (like Unicode).

Engineers also confuse tries with hash tables. Hash tables are better for exact lookups, but tries excel at prefix matching. If you need "find all words starting with 'cat'", a trie is O(m) while a hash table is O(n) where n is total words.

Another common mistake is not handling deletion correctly. Deleting a word from a trie requires careful node cleanup—you can't just remove the leaf node if it's part of another word's path. This requires tracking whether a node marks the end of a word and whether it has children.

How This Breaks Systems in the Real World

A search engine was using a hash table to store search suggestions. When users typed "java", the system needed to find all queries starting with "java" (like "java tutorial", "javascript", "java vs python"). The hash table required scanning all stored queries, which became O(n) and slow as the database grew to millions of queries. The fix? Switch to a trie. Now prefix queries are O(m) where m is the typed prefix length, making autocomplete instant even with millions of stored queries.

Another story: A network router was using a simple array to store IP routing rules. When a packet arrived, the router needed to find the longest matching prefix. With an array, this required checking every rule (O(n)). As routing tables grew, packet forwarding became a bottleneck. The fix? Use a trie (specifically a compressed trie/radix tree). Longest prefix matching became O(m) where m is the IP address length (32 bits for IPv4), making routing fast and scalable.

What is a Trie?

A trie is a tree where each node represents a character, and paths from root to leaf nodes spell out words. The root represents an empty string, and each edge represents a character.

Structure

        (root)
       /  |  \
      a   b   c
     /|   |   |
    p t   a   a
   /  |   |   |
  p   e   t   t
  |       |
  l       e
  |
  e

This trie stores: "apple", "ate", "bat", "cat"

Key Properties

• Prefix sharing: Words with common prefixes share nodes
• Fast prefix search: Finding all words with a prefix is O(m) where m is prefix length
• Space efficient for many similar strings: Shared prefixes reduce storage
• Character-based: Each node typically has up to 26 children (for lowercase English)

Trie Implementation

Basic Trie Node

1class TrieNode {
2  children: Map<string, TrieNode> = new Map();
3  isEndOfWord: boolean = false;
4}
5
6class Trie {
7  private root: TrieNode;
8
9  constructor() {
10    this.root = new TrieNode();
11  }
12
13  // Insert a word into the trie
14  insert(word: string): void {
15    let current = this.root;

Advanced Operations

Find All Words with Prefix

1// Find all words starting with a prefix
2findWordsWithPrefix(prefix: string): string[] {
3  const result: string[] = [];
4  let current = this.root;
5  
6  // Navigate to prefix node
7  for (const char of prefix) {
8    if (!current.children.has(char)) {
9      return result; // No words with this prefix
10    }
11    current = current.children.get(char)!;

Delete Word from Trie

1delete(word: string): boolean {
2  return this.deleteHelper(this.root, word, 0);
3}
4
5private deleteHelper(node: TrieNode, word: string, index: number): boolean {
6  if (index === word.length) {
7    // Reached end of word
8    if (!node.isEndOfWord) {
9      return false; // Word doesn't exist
10    }
11    node.isEndOfWord =

Common Pitfalls

1. Not marking end of word: Forgetting to set isEndOfWord = true causes search to fail even when word exists
2. Incorrect deletion: Deleting nodes that are part of other words breaks the trie
3. Space inefficiency: Using arrays of size 26 for each node wastes space when most children are null
4. Case sensitivity: Not handling uppercase/lowercase consistently causes search failures
5. Empty string handling: Not handling empty string as valid input causes edge case bugs

Failure Stories You'll Recognize

A spell checker was using a hash table to store dictionary words. When users typed "appl", the system needed to suggest "apple", "apply", "application". The hash table couldn't efficiently find words by prefix, so it scanned all words (O(n)). With a 100,000 word dictionary, this was slow. The fix? Use a trie. Prefix suggestions became O(m) where m is typed length, making suggestions instant.

Another story: A service was building an autocomplete feature. It stored all queries in a database and used SQL LIKE 'prefix%' queries. As the database grew, these queries became slow (full table scans). The fix? Build a trie in memory from frequently used queries. Autocomplete became O(m) instead of O(n), making it fast enough for real-time suggestions.

What Interviewers Are Really Testing

• Recognition: Can you identify when prefix matching is the core requirement?
• Space-time trade-offs: Do you understand tries use more space but enable faster prefix queries?
• Tree traversal: Can you implement DFS for collecting words with a prefix?
• Edge cases: Do you handle empty strings, single characters, and deletion correctly?
• Alternatives: Can you explain when hash tables or BSTs might be better?

Interview Questions

Beginner

1. Implement a trie with insert, search, and startsWith operations
2. Find if a word exists in a trie
3. Count how many words start with a given prefix

Intermediate

1. Find all words with a given prefix
2. Delete a word from a trie
3. Find the longest common prefix of all words in a trie
4. Implement autocomplete using a trie

Senior

1. Implement a compressed trie (radix tree) to save space
2. Design a search engine autocomplete system using tries
3. Implement a trie that supports wildcard matching (e.g., "c*t" matches "cat", "cut")
4. Optimize trie for memory usage when character set is large (Unicode)

1. Tries excel at prefix matching: O(m) time for prefix queries vs O(n) for hash tables
2. Space-time trade-off: Tries use more memory but enable faster prefix operations
3. Character-based structure: Each node represents a character, paths spell words
4. Prefix sharing: Words with common prefixes share nodes, saving space
5. Use cases: Autocomplete, spell checkers, IP routing, dictionary problems
6. Deletion requires care: Must check if node is part of another word before deleting
7. Consider compressed tries: Radix trees save space by merging single-child nodes
8. Character set matters: Large character sets (Unicode) increase space usage significantly
9. Alternative structures: Hash tables better for exact lookups, tries better for prefix queries
10. Recognition is key: Knowing when prefix matching is the requirement is half the solution

• Trees - Understanding tree structures
• Hash Tables - Alternative for exact lookups
• String Algorithms - String matching and search
• Recursion - Essential for trie traversal