Trie (dibaca "try") adalah tree khusus untuk menyimpan string. Setiap node mewakili satu karakter, dan path dari root ke node membentuk sebuah kata.

Keunggulan Trie vs Hash Map untuk string:

• Pencarian prefix: O(m) di mana m = panjang prefix
• Autocomplete sangat efisien
• Tidak perlu hash function

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

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

  // Sisipkan kata — O(m)
  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEnd = true;
  }

  // Cari kata persis — O(m)
  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEnd;
  }

  // Cari prefix — O(m)
  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

const trie = new Trie();
trie.insert("belajar");
trie.insert("beli");
trie.insert("belanja");

trie.search("belajar");    // true
trie.search("bela");       // false (bukan kata utuh)
trie.startsWith("bel");    // true (ada kata dengan prefix "bel")

Kegunaan nyata:

• Autocomplete — search bar suggestion
• Spell checker — deteksi kata yang tidak ada
• IP routing — longest prefix match
• T9 keyboard — prediksi kata dari angka

🎭 Analogi sehari-hari: Trie = kamus tebal yang disusun per huruf. Mau cari kata "belajar"? Buka section "B", lalu "BE", "BEL", "BELA"... satu huruf per langkah. Mau autocomplete kata yang mulai "bel"? Tinggal lihat semua kata di section "BEL". Itulah trie — efisien karena prefix yang sama dipake bersama.

💡 Trie vs Hash Map untuk autocomplete: Hash Map cek "kata X ada gak" itu O(1), tapi autocomplete (semua kata mulai prefix "bel") butuh scan semua key = O(n × m). Trie bisa langsung navigasi ke node "bel" lalu DFS dari situ = O(jumlah kata yang match). Untuk autocomplete real-time, Trie menang jauh.

⚠️ Jebakan umum:

• Memory boros untuk dictionary kecil — kalau cuma 1000 kata, Hash Map jauh lebih hemat. Trie shine di skala besar
• Lupa flag isEnd = "bel" dianggap sebagai kata padahal cuma prefix dari "belajar"
• Karakter di luar ASCII (emoji, unicode) = perlu support map dinamis, bukan array fixed-size
• Case sensitive vs insensitive harus diputuskan (lowercase semua dulu sebelum insert?)

🎯 Trie vs Hash Map vs BST untuk string?

• Exact match cepat → Hash Map (O(1))
• Prefix search/autocomplete → Trie (O(panjang prefix))
• Sorted iteration → BST/Trie
• Memory minimal → Hash Map
• Banyak prefix yang shared → Trie (compression)

🧪 Tebakan cepat: Insert "belajar", "beli", "belanja". Berapa node? Root + b + e + l (shared) + a/i (branch) + ... = ~12 node. Vs 3 hash map entries. Lebih boros memori, tapi prefix query jauh lebih cepat.

TL;DR: Trie = tree per-karakter untuk string. Prefix search O(m). Pilih untuk autocomplete, spell-check, IP routing. Hindari kalau cuma exact-match (Hash Map lebih hemat).