🌇DSA
← Back
Data StructureAdvanced
🌴

Tries

Prefix-based word lookup tree

⏱️ 6–10 hours🧩 10 LeetCode
🔒 Login to unlock solutions and track progress. Login

What is it?

A trie (rhymes with "try") is like a filing cabinet organised letter by letter. Each drawer is a letter; open them in sequence to spell a word.

  • Each node represents a single character.
  • A path from root to a marked node spells a complete word.
  • Perfect for prefix lookups — type "ca" and instantly find "cat", "car", "cake".

Variants / Subtypes

  • Standard Trie — one node per character
  • Compressed Trie (Radix/Patricia) — merges chains of single children
  • Ternary Search Tree — more memory-efficient alternative

Real-World Examples

Keyboard autocomplete
Search bar suggestions
Spell checker
Contact prefix search
URL router matching
Word games like Boggle

Code Example

What this code shows

Insert 'cat' and 'car' into the trie. Search 'cat' → true because a node marked end=true exists. Search 'cab' → false because there is no 'b' branch after 'ca'.

class TrieNode {
constructor() {
  this.children = {}; // one key per character
  this.isEnd    = false; // true if a word ends here
}
}

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

insert(word) {
  let node = this.root;
  for (const ch of word) {
    // create child node if it doesn't exist
    node.children[ch] ??= new TrieNode();
    node = node.children[ch]; // move down
  }
  node.isEnd = true; // mark end of word
}

search(word) {
  let node = this.root;
  for (const ch of word) {
    if (!node.children[ch]) return false; // path missing
    node = node.children[ch];
  }
  return node.isEnd; // must be a complete word, not just a prefix
}
}

const trie = new Trie();
trie.insert("cat");
trie.insert("car");
console.log(trie.search("cat")); // true  — 'cat' was inserted
console.log(trie.search("cab")); // false — no 'b' after 'ca'

Expected Output

search('cat'): true
search('cab'): false

LeetCode Practice