📖 Trie (Prefix Tree)

A Trie (pronounced "Try") is a special type of tree used to store associative data structures. A common use for Tries is storing an entire dictionary for quick lookups and Prefix Search.

💡 The Logic (ELI5)

Think of Autocomplete on your phone:

You start typing "H-E-L".
The phone looks at a giant tree.
It starts at the root, Goes to the 'H' branch, then the 'E' branch, then 'L'.
From the 'L' branch, it sees all possible words like "Hello", "Help", "Hell".
It suggests these words to you. Every node in the tree is a single character!

🔍 The Deep Dive

Complexity Analysis ($L$ = Word length)

Insert: $O(L)$
Search: $O(L)$
Prefix Search: $O(L)$
Space: $O(L \times N)$ where $N$ is number of words. (Can be memory intensive!).

Key Characteristic

Nodes do not store the word itself. Instead, their position in the tree defines the word. Every node typically contains an array of 26 pointers (for 'a' to 'z') and a boolean flag isEndOfWord.

🛠️ Code Forge: Trie Implementation


javascript Standard
class TrieNode {
  constructor() {
    this.children = {}; // Using an object for flexibility
    this.isEndOfWord = false;
  }
}

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

  insert(word) {
    let curr = this.root;
    for (let char of word) {
      if (!curr.children[char]) {
        curr.children[char] = new TrieNode();
      }
      curr = curr.children[char];
    }
    curr.isEndOfWord = true;
  }

  search(word) {
    let curr = this.root;
    for (let char of word) {
      if (!curr.children[char]) return false;
      curr = curr.children[char];
    }
    return curr.isEndOfWord;
  }

  startsWith(prefix) {
    let curr = this.root;
    for (let char of prefix) {
      if (!curr.children[char]) return false;
      curr = curr.children[char];
    }
    return true;
  }
}

🎯 Interview Pulse

Top Use Cases

Autocomplete / Typeahead.
IP Routing (Longest Prefix Match).
Spell Checkers.
Word Search puzzles.