Frontend Beauty
ESC

Type to search the knowledge base.

Implement Trie

Prefix tree with insert, search, startsWith — node children map, end flag, and complexity for autocomplete-style use.

intermediate3 min read
  • dsa
  • trie
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Implement a trie (prefix tree):

  • insert(word)
  • search(word) — true if word was inserted
  • startsWith(prefix) — true if any word has this prefix
insert("apple")
search("apple") → true
search("app") → false
startsWith("app") → true
insert("app")
search("app") → true

Why not a Set?

startsWith on a Set of words is O(n · L) scan. Trie answers prefix in O(L).

Implementation

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) {
        node.children.set(ch, new TrieNode());
      }
      node = node.children.get(ch)!;
    }
    node.isEnd = true;
  }

  private walk(s: string): TrieNode | null {
    let node = this.root;
    for (const ch of s) {
      const next = node.children.get(ch);
      if (!next) return null;
      node = next;
    }
    return node;
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return !!node && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.walk(prefix) !== null;
  }
}
op time space
insert O(L) O(L) new nodes worst
search / startsWith O(L) O(1)

Total space O(total characters inserted) with sharing.

Array of 26 children

If only lowercase a–z:

children: (TrieNode | undefined)[] = Array(26);
// index = ch.charCodeAt(0) - 97

Slightly faster; Map is flexible for interviews with mixed charset.

Edge cases

  • Empty string (constraints vary)
  • insert same word twice
  • prefix that equals a word
  • long shared prefixes (app, apple, apply)

Common mistakes

  • search returning true on prefix without isEnd
  • Not creating nodes on insert
  • Sharing one node incorrectly across branches

Interview delivery

  1. Prefix problem → trie.
  2. Node = children + end flag.
  3. Implement three methods.
  4. Contrast with hash set.
  5. O(L) ops.

Mental model

Tries trade memory for shared-prefix lookups. Each edge is a character; a boolean marks word ends so "app" and "apple" can coexist.

Autocomplete, spellcheck, IP routing (bitwise tries), and T9-style search all use this shape.

Complexity table

Op Time Notes
insert O(L) may allocate L nodes
search O(L) needs isEnd
startsWith O(L) any node suffices

Out-loud answer

“Prefix tree: nodes with children map and isEnd. Insert creates path and marks end. Search walks and requires isEnd; startsWith only needs the walk to succeed. O(L) per op.”

Interview delivery

  1. Why trie beats set for prefixes.
  2. Node structure.
  3. insert / search / startsWith.
  4. search needs isEnd; startsWith doesn’t.
  5. O(L) time, space shared prefixes.

Tiny test plan

insert apple; search app → false; startsWith app → true; insert app; search app → true; search apple → true.

Further reading