Implement Trie (Prefix Tree)

Difficulty: Medium

Design a data structure that stores a set of words and can quickly answer two kinds of questions about them: "is this exact word in the set?" and "does any word in the set start with this prefix?"

Build a class with three operations:

  • insert(word) - adds a word to the structure.
  • search(word) - returns true only if that exact word was previously inserted.
  • startsWith(prefix) - returns true if any inserted word begins with that prefix (the prefix itself doesn't need to have been inserted as a whole word).

Examples

Input: insert("apple"); search("apple"); search("app"); startsWith("app"); insert("app"); search("app")
Output: undefined, true, false, true, undefined, true

"apple" is inserted, so search("apple") is true. search("app") is false because "app" was never inserted on its own - but startsWith("app") is true because "apple" starts with "app". After inserting "app" directly, search("app") becomes true too.

Input: insert("cat"); search("car"); startsWith("ca")
Output: undefined, false, true

"car" was never inserted, so search returns false, even though "cat" shares the prefix "ca".

Constraints

  • 1 <= word.length, prefix.length <= 2000

  • word and prefix consist only of lowercase English letters

  • At most 3 * 10^4 calls total to insert, search, and startsWith

Approach

The key insight is that many words share prefixes ("app" and "apple" both start with "a" -> "p" -> "p"). A trie (prefix tree) exploits this by giving each letter position its own node, shared across every word that agrees up to that point. Starting at a root node, each node holds links to its possible next letters (its children) plus a boolean flag for "a word ends here."

insert walks the word letter by letter, creating child nodes as needed, and marks the final node as a word-ending. search walks the same way but fails if any letter is missing, and requires the final node's flag to be set. startsWith is identical to search except it doesn't check that flag - just that the path exists.

Solutions

Brute Force - Array of Words

Keep every inserted word in a plain array. search() checks for an exact match; startsWith() checks whether any stored word begins with the given prefix. Simple, but every lookup scans the whole collection.

class Trie {
  constructor() {
    this.words = [];
  }

  insert(word) {
    this.words.push(word);
  }

  search(word) {
    return this.words.includes(word);
  }

  startsWith(prefix) {
    return this.words.some((w) => w.startsWith(prefix));
  }
}

Time: O(L) for insert, O(n * L) for search/startsWith, where n is the number of stored words and L is average word length · Space: O(n * L) to store all the words

Optimal - Trie Node Tree

Build an actual tree of letters. Each node has a map from letter to child node, plus a flag for whether a word ends there. Inserting, searching, and checking a prefix all just walk down the tree one letter at a time.

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

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

  insert(word) {
    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.isWord = true;
  }

  // Walks the given string letter by letter; returns the node at the end
  // of the path, or null if the path doesn't fully exist.
  _walk(str) {
    let node = this.root;
    for (const ch of str) {
      if (!node.children.has(ch)) return null;
      node = node.children.get(ch);
    }
    return node;
  }

  search(word) {
    const node = this._walk(word);
    return node !== null && node.isWord;
  }

  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
}

Time: O(L) for every operation, where L is the length of the word/prefix involved · Space: O(N) total across all nodes, where N is the total number of letters inserted (shared prefixes reuse nodes)