Trie Pattern

Why this pattern matters for LeetCode

A hash map of words tells you if an exact word exists in O(1), but it can't tell you if any word starts with a given prefix without scanning every key. A trie stores strings character by character in a tree, so all words sharing a prefix share the same path from the root. Prefix lookups take O(m) time, the length of the prefix, not the size of the dictionary. This is why autocomplete, spell-check, and word search problems reach for tries.

What the Trie pattern is

A trie (prefix tree) is a tree where each node represents one character. Each path from the root to a terminal node spells a complete word. To insert a word, walk character by character from the root, creating nodes for characters that don't yet exist, and mark the final node as a word ending. To search, walk the same path and check if the final node is marked as a word end. To check a prefix, walk the path without requiring the end node to be marked, if the path exists, the prefix exists.

Reach for Trie when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Trie

• ✓Implement Trie, build insert, search, and startsWith from scratch
• ✓Search Suggestions System, return words sharing a prefix for autocomplete
• ✓Word Search II, find all words from a dictionary in a grid (trie + DFS)
• ✓Replace Words, replace words with their shortest dictionary root prefix
• ✓Design Add and Search Words, search with wildcard '.' characters

When NOT to use Trie

• ✕You only need exact word lookup with no prefix queries, a Set or hash map is simpler
• ✕The input set is tiny, a linear scan of an array is clearer and fast enough
• ✕You need fuzzy matching (edit distance) rather than exact prefix matching, different algorithm
• ✕Memory is severely constrained, tries use O(n × m × alphabet_size) in the worst case

Better alternative: In those cases, a hash map or Set handles exact lookups in O(1), and Levenshtein distance handles fuzzy matching.

JavaScript code template

Implement Trie. O(m) per insert, search, and startsWith

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

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

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd; // path exists AND it ends a complete word
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true; // path exists, prefix is present
  }
}

Each TrieNode holds a children object (character → child node) and an isEnd flag. Insert walks character by character, creating new nodes where needed, and marks the last node as a word end. Search walks the same path and requires isEnd = true at the final node, a path that exists but isn't marked means the search string is only a prefix of a stored word, not a word itself. startsWith is identical to search except it doesn't check isEnd.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create a root TrieNode, the empty-string starting point.
2. 2For insert: walk character by character from the root, creating new TrieNode children where none exist.
3. 3After the last character of insert, set node.isEnd = true to mark a complete word.
4. 4For search: walk character by character. If any character is missing from children, return false. At the end, return node.isEnd.
5. 5For startsWith: same walk as search, but return true regardless of isEnd, if the path exists, the prefix exists.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

Coming soon

• Implement Trie (Prefix Tree)

  Build insert, search, and startsWith from scratch, the canonical trie problem.

  Coming soon
• Search Suggestions System

  Insert all products into a trie. For each prefix of the search term, collect up to 3 lexicographically smallest matches.

  Coming soon
• Word Search II

  Build a trie from the word list, then DFS the grid. Prune DFS branches that don't match any trie prefix.

  Coming soon
• Design Add and Search Words

  Like Implement Trie, but search must handle '.' wildcards, recurse into all children when you hit a dot.

  Coming soon

Common mistakes beginners make

• ✕Confusing search and startsWith, search requires isEnd = true at the last node; startsWith does not. A string that is only a prefix of a stored word returns false for search and true for startsWith.
• ✕Not checking if the child node exists before accessing it, if a character is missing, node.children[char] is undefined and accessing its children crashes.
• ✕Building a trie when a hash set would do, if the problem only needs exact-word lookup with no prefix queries, a Set is simpler and uses less memory.
• ✕Using an array of 26 instead of a hash object and not handling the index correctly, an array works for lowercase English letters but requires char.charCodeAt(0) - 97 arithmetic. A plain object {} is simpler and works for any character set.

Trie vs Hash Map vs Set

Choose the right tool for the job.

Time and space complexity

Each operation walks at most m characters. O(m) per call. Space is proportional to the total number of characters stored across all words. In the worst case, n words of average length m with no shared prefixes require n × m nodes. In practice, shared prefixes reduce this significantly.

Frequently asked questions

When should I use a trie instead of a hash set?

Use a trie when the problem involves prefix queries, checking if a word starts with a given prefix, or collecting all words that share a prefix. A hash set can't answer prefix queries without scanning every key. If the problem only needs exact word lookup, a hash set is simpler and uses less memory.

Why is startsWith O(m) and not O(n)?

Because you're walking the trie path for the prefix, m characters, m node hops. The number of words in the trie (n) doesn't matter. You never look at words that diverged at a different character. This is the trie's key advantage over scanning a list of words.

What's the difference between isEnd and not isEnd?

Both 'app' and 'apple' share the path a → p → p. If you only inserted 'apple', the node at the second 'p' has isEnd = false (it's a prefix, not a complete word). If you also inserted 'app', that node has isEnd = true. search('app') returns true only if that node's isEnd is true. startsWith('app') returns true regardless.

Do I always implement Trie from scratch in interviews?

If the problem is literally 'Implement Trie,' yes. For problems that use a trie as a tool (Word Search II, Search Suggestions), you implement the trie as part of the broader solution. JavaScript has no built-in trie, so you'll always write the TrieNode class and the insert/search/startsWith methods yourself.