Trie

Prefix tree for efficient string search, autocomplete, and word matching.

5 problems 0 Easy 4 Medium 1 Hard

Overview

A Trie (prefix tree) stores strings character by character, enabling O(m) search where m is the word length. It is the go-to structure for prefix queries and word dictionaries.

When to Use

Implement Trie (insert/search/startsWith)
Word search II
Design add/search words
Replace words
Autocomplete

Common Mistakes

Forgetting the isEnd flag on the last character
Memory overhead — each node has 26 children pointers
Using string concatenation in DFS — pass index instead

Complexity

Time

O(m) per operation where m is word length

Space

O(ALPHABET_SIZE × m × n)

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

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

  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(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }
}

Problems (5)

Hide completed

Problem	Difficulty	Companies	Freq
Implement Trie (Prefix Tree)	Medium	AmazonGoogle +2	High
Design Add and Search Words Data Structure	Medium	FacebookBloomberg	Medium
Word Search II	Hard	AmazonMicrosoft +1	Medium
Longest Word in Dictionary	Medium	Google	Low
Replace Words	Medium	FacebookAmazon	Medium

Tries solve prefix-matching and autocomplete in O(L) time, beating hash maps for prefix queries. Ful…

Enjoying this free content?

If this saved you time, buying me a coffee keeps new content coming.

☕ Buy me a coffee