Implement Trie (Prefix Tree)

MediumTriesTrieHash TableStringDesign

Problem

Design a data structure that stores a set of strings and supports three operations: insert a word, check whether an exact word has been inserted, and check whether any inserted word starts with a given prefix. All operations should stay fast even as the dictionary grows large.

Example. After inserting "apple", searching for "apple" returns true, searching for "app" returns false since no exact word "app" was inserted, but checking the prefix "app" returns true.

Key idea

A plain hash set can check exact membership quickly, but it cannot answer "does any word start with this prefix" without scanning every stored string. The fix is to stop storing whole words and instead store shared structure: build a tree where each node represents one character position, and a path from the root spells out a prefix.

Each node holds a small table of children, one per possible next character, plus a flag marking whether a complete word ends there. Inserting a word walks down the tree one character at a time, creating missing nodes as needed, and marks the final node as a word ending. Search follows the same walk: an exact-word search also requires the end flag to be set, while a prefix search only requires the walk to complete without falling off the tree. Because every operation is just a chain of character lookups, the cost depends only on the string's length, never on how many other words are stored.

Solution

class TrieNode {
  children: Map<string, TrieNode> = new Map(); // one entry per next character
  isEnd: boolean = false;
}

class Trie {
  private readonly root: TrieNode = new TrieNode();

  insert(word: string): void {
    let node = this.root;
    for (const char of word) {
      let child = node.children.get(char);
      if (!child) {
        child = new TrieNode();
        node.children.set(char, child);
      }
      node = child;
    }
    node.isEnd = true; // mark the final node as a complete word
  }

  search(word: string): boolean {
    const node = this.walk(word);
    return node !== null && node.isEnd; // must be a full word, not just a prefix
  }

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

  private walk(chars: string): TrieNode | null {
    // shared traversal used by both search and startsWith
    let node = this.root;
    for (const char of chars) {
      const child = node.children.get(char);
      if (!child) {
        return null;
      }
      node = child;
    }
    return node;
  }
}

Complexity

  • Time: O(L) per insert, search, or prefix check, where L is the length of the word or prefix.
  • Space: O(total characters inserted). Shared prefixes reuse the same nodes.

Watch out for

  • Distinguish "prefix exists" from "word exists": a node being reachable does not mean a word ends there.
  • Reuse a character's child node when it already exists instead of creating a new one. That reuse is what makes shared prefixes cheap.

Pattern

This is the foundational trie pattern: trade per-character node storage for prefix-time queries. It underlies autocomplete and spell-checkers, and is the building block for harder trie problems that add wildcard search or run a grid search against a dictionary.

Related questions