14. Trie (Prefix Tree)

TL;DR

A trie is a rooted tree where each edge is labeled with a character; paths from the root spell prefixes. It supports insert, exact search, and startsWith in O(L) per string length L. Nodes often hold children maps or fixed arrays plus an isEnd flag. Advanced uses: wildcard DFS, board search with trie pruning, and autocomplete with frequency heaps at nodes.

Core Basics

• Object: prefix tree sharing nodes; path from root spells a string; children map char→node.
• Cost profile: insert/search (O(L)) for length (L); beats hash for prefix enumeration and autocomplete.
• Staff-level bar: discuss memory explosion vs compressed trie / double-array tries at scale.

Recognition Cues

• Phrases: “prefix,” “dictionary,” “autocomplete,” “replace shortest root,” “search words on board,” “. wildcard.”
• Input: many strings + many queries; or 2D grid of letters.
• Output: boolean existence, list of words, or ranked suggestions.

Use-case Lens

• Best when: many string queries share prefixes: autocomplete, prefix existence, dictionary pruning, or word search.
• Not for: one-off string lookup; a hash set is simpler.
• Main invariant: every edge consumes one character, so reaching a node means the prefix exists.
• Interview move: explain whether terminal flags, counts, or top suggestions are stored at nodes.

Diagram

Step-by-step Visual

Example: Insert "cat" and "car", then search "cap". A Trie shares prefixes and marks full words with terminal flags.

Understanding

Sharing prefixes collapses storage: "apple" and "apply" share "appl". Walking the trie is one step per character. Wildcards branch all children at that level. On a board, DFS from each cell but descend the trie so you never chase words with impossible next letters.

Generic Recipe

1. Node: map or array children, isEnd (or word count).
2. Insert: walk/create nodes per rune; mark terminal at last.
3. Search / startsWith: walk; fail if missing child; check isEnd for full word.
4. Wildcard: at ., recurse every non-nil child; short-circuit on first success if problem allows.
5. Word Search II: build trie from words; DFS grid with visited bitmask/matrix; prune trie leaves when word fully found (optional optimization).

Complexity

• Time: O(L) per op for plain walks; wildcard O(alphabet^wildcards × L) worst; board DFS bounded by cells × branching with trie cut.
• Space: O(total characters) stored across dictionary strings (shared prefixes).

Memory Hooks

• Operational mantra: walk one character per edge; shared prefixes turn repeated string scans into one tree path.
• Anti-panic: ask whether work is shared by prefixes; if not, a hash set or sorting may beat a trie.

Study Pattern (SDE3+)

• Recognition drill (10 min): separate exact lookup, prefix lookup, wildcard search, board pruning, and autocomplete ranking.
• Implementation sprint (25 min): code insert/search/startsWith plus wildcard DFS.
• Staff follow-up (10 min): discuss memory blowup, compressed tries, deletion, ranking, and Unicode alphabet size.

Generic Code Template

Go

type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

func NewTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: NewTrieNode()}
}

func (trie *Trie) Insert(word string) {
	current := trie.root
	for _, character := range word {
		if current.children[character] == nil {
			current.children[character] = NewTrieNode()
		}
		current = current.children[character]
	}
	current.isEnd = true
}

func (trie *Trie) Search(word string) bool {
	current := trie.root
	for _, character := range word {
		next := current.children[character]
		if next == nil {
			return false
		}
		current = next
	}
	return current.isEnd
}

func (trie *Trie) StartsWith(prefix string) bool {
	current := trie.root
	for _, character := range prefix {
		next := current.children[character]
		if next == nil {
			return false
		}
		current = next
	}
	return true
}

JavaScript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let current = this.root;
    for (const character of word) {
      if (!current.children.has(character)) {
        current.children.set(character, new TrieNode());
      }
      current = current.children.get(character);
    }
    current.isEnd = true;
  }

  search(word) {
    let current = this.root;
    for (const character of word) {
      if (!current.children.has(character)) return false;
      current = current.children.get(character);
    }
    return current.isEnd;
  }

  startsWith(prefix) {
    let current = this.root;
    for (const character of prefix) {
      if (!current.children.has(character)) return false;
      current = current.children.get(character);
    }
    return true;
  }
}

Variants

• Word dictionary: basic insert/search/startsWith.
• Wildcard search: trie DFS — at . try every child key.
• Word Search II: trie + backtracking on board; remove words from trie after found to prune.
• Autocomplete top-k: at each node keep min-heap or sorted list of top k by weight/frequency; on prefix, walk trie then read heap (or use sort + binary search alternative from index).

Representative Problems

• 208. Implement Trie (Prefix Tree) — core API
• 211. Design Add and Search Words Data Structure — wildcard DFS
• 212. Word Search II — board + trie pruning
• 1268. Search Suggestions System — autocomplete / ranking

Anti-patterns

• Storing full strings at every node instead of isEnd — wastes space.
• Board DFS without trie: revisits impossible prefixes repeatedly.
• Wildcard search as linear scan of full dictionary each query whenmany queries dominate.
• Forgetting backtrack unvisit on grid (reuse board state incorrectly).