21. Trie (Prefix Tree)

🧸 ELI5: A trie is like a tree where each branch is a single letter, and words that share the same beginning share the same branches. "CAT" and "CAR" share the "CA" branch, then split into "T" and "R". This is exactly how your phone keyboard guesses what you're about to type.

🌍 Real life: Autocomplete/predictive text on your phone. Search engine "did you mean" and autosuggest dropdowns. Spell checkers.

📝 Pseudocode:

trieNode = { children: {}, isEndOfWord: false }

function insert(root, word):
    node = root
    for letter in word:
        if letter not in node.children:
            node.children[letter] = new trieNode()
        node = node.children[letter]
    node.isEndOfWord = true

function search(root, word):
    node = root
    for letter in word:
        if letter not in node.children: return false
        node = node.children[letter]
    return node.isEndOfWord

🐹 Go:

package main

import "fmt"

type TrieNode struct {
	children map[rune]*TrieNode
	isWord   bool
}

func newTrieNode() *TrieNode {
	return &TrieNode{children: make(map[rune]*TrieNode)}
}

type Trie struct {
	root *TrieNode
}

func NewTrie() *Trie {
	return &Trie{root: newTrieNode()}
}

func (t *Trie) Insert(word string) {
	node := t.root
	for _, letter := range word {
		if node.children[letter] == nil {
			node.children[letter] = newTrieNode()
		}
		node = node.children[letter]
	}
	node.isWord = true
}

func (t *Trie) Search(word string) bool {
	node := t.root
	for _, letter := range word {
		if node.children[letter] == nil {
			return false
		}
		node = node.children[letter]
	}
	return node.isWord
}

func main() {
	keyboard := NewTrie()
	keyboard.Insert("cat")
	keyboard.Insert("car")

	fmt.Println(keyboard.Search("cat")) // true
	fmt.Println(keyboard.Search("ca"))  // false (only a prefix, not a full word)
}

🇨 C — Go's version uses a map[rune]*TrieNode per node; C swaps that for a fixed 26-pointer array indexed by letter - 'a', trading "any Unicode letter" for "no hash map needed":

#include <stdio.h>
#include <stdlib.h>

typedef struct TrieNode {
    struct TrieNode *children[26];
    int is_word;
} TrieNode;

TrieNode *trie_new_node(void) { return calloc(1, sizeof(TrieNode)); }

void trie_insert(TrieNode *root, const char *word) {
    TrieNode *node = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!node->children[idx]) node->children[idx] = trie_new_node();
        node = node->children[idx];
    }
    node->is_word = 1;
}

int trie_search(TrieNode *root, const char *word) {
    TrieNode *node = root;
    for (int i = 0; word[i]; i++) {
        int idx = word[i] - 'a';
        if (!node->children[idx]) return 0;
        node = node->children[idx];
    }
    return node->is_word;
}

void trie_free(TrieNode *node) {
    if (!node) return;
    for (int i = 0; i < 26; i++) trie_free(node->children[i]);
    free(node);
}

int main(void) {
    TrieNode *keyboard = trie_new_node();
    trie_insert(keyboard, "cat");
    trie_insert(keyboard, "car");

    printf("%d\n", trie_search(keyboard, "cat")); // 1 (true)
    printf("%d\n", trie_search(keyboard, "ca"));   // 0 (false — only a prefix, not a full word)

    trie_free(keyboard);
    return 0;
}

⏱️ Complexity: Insert/search = O(k) where k is the word length — independent of how many other words are stored! That's why autocomplete feels instant even with a huge dictionary.