Trie

Trie

A Trie (prefix tree) is a tree-like data structure used for efficiently storing and searching strings. Each node represents a single character, and paths from root to marked nodes form complete words.

Node Structure

class TrieNode {
  constructor() {
    this.children = {};   // char → TrieNode
    this.isEnd = false;   // marks end of a word
  }
}

Insert

Walk down the tree character by character, creating nodes as needed. Mark the last node as a word end.

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

Search

Walk down the tree for each character. Return true only if every character exists and the final node is marked as a word end.

StartsWith (Prefix Search)

Same as search, but you don't need isEnd to be true — just confirm every character in the prefix exists.

Complexity

Where m is the length of the word or prefix.

Real-World Uses

• Autocomplete and search suggestions
• Spell checkers
• IP routing (longest prefix match)
• Word games (Boggle, Scrabble)

Your Task

Implement a Trie class with insert, search, and startsWith methods.