#208 - Implement Trie (Prefix Tree)

MediumTrie

Implement a trie with insert, search, and startsWith methods.

• insert(word) – inserts the string word into the trie.
• search(word) – returns true if the exact string word is in the trie.
• startsWith(prefix) – returns true if any previously inserted string has the prefix prefix.

Input	Output
Operations	Output
insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")	[null, true, false, true, null, true]

Solution Space

Try it

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

/**
 * Prefix tree supporting insert, exact search, and prefix search.
 */
export 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;
  }

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

  startsWith(prefix: string): boolean {
    return this.traverse(prefix) !== null;
  }

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

Approach: trie with hash-map children – each node stores a `Map<char, TrieNode>` and an `isEnd` flag. `search` requires `isEnd` at the final node; `startsWith` does not.

Time: O(L) per operation – where L is the length of the word/prefix.

Space: O(T) total – where T is the total number of characters across all inserted words.

#1318 Minimum Flips to Make a OR b Equal to c

#1268 Search Suggestions System