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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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).

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).