🔤 Trie (Prefix Tree)

🔴 Advanced Advanced 60 min read

🎯 What is a Trie?

A Trie (pronounced "try") is a tree-like data structure for efficiently storing and searching strings. Each node represents a character, and paths from root to leaf form complete words. Tries enable O(L) operations where L is word length - independent of the total number of stored words!

Root
 │
 ├── c → a → t (✓)  ← word "cat"
 │         └── s (✓) ← word "cats"
 │
 ├── d → o → g (✓)  ← word "dog"
 │
 └── b → a → t (✓)  ← word "bat"
           └── s (✓) ← word "bats"

✓ marks end of word

💻 PHP Implementation

<?php
class TrieNode {
    /** @var array */
    public array $children = [];
    public bool $isEndOfWord = false;
}

class Trie {
    private TrieNode $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    // Insert word - O(L) where L = word length
    public function insert(string $word): void {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    // Search exact word - O(L)
    public function search(string $word): bool {
        $node = $this->getNode($word);
        return $node !== null && $node->isEndOfWord;
    }

    // Check if any word starts with prefix - O(L)
    public function startsWith(string $prefix): bool {
        return $this->getNode($prefix) !== null;
    }

    private function getNode(string $str): ?TrieNode {
        $node = $this->root;
        for ($i = 0; $i < strlen($str); $i++) {
            $char = $str[$i];
            if (!isset($node->children[$char])) return null;
            $node = $node->children[$char];
        }
        return $node;
    }

    // Get all words with given prefix (autocomplete)
    public function autocomplete(string $prefix): array {
        $result = [];
        $node = $this->getNode($prefix);
        if ($node !== null) {
            $this->collectWords($node, $prefix, $result);
        }
        return $result;
    }

    private function collectWords(TrieNode $node, string $currentWord, array &$result): void {
        if ($node->isEndOfWord) $result[] = $currentWord;
        foreach ($node->children as $char => $child) {
            $this->collectWords($child, $currentWord . $char, $result);
        }
    }

    // Delete word - O(L)
    public function delete(string $word): bool {
        return $this->deleteRec($this->root, $word, 0);
    }

    private function deleteRec(TrieNode $node, string $word, int $depth): bool {
        if ($depth === strlen($word)) {
            if (!$node->isEndOfWord) return false;
            $node->isEndOfWord = false;
            return empty($node->children);
        }
        $char = $word[$depth];
        if (!isset($node->children[$char])) return false;

        $shouldDelete = $this->deleteRec($node->children[$char], $word, $depth + 1);
        if ($shouldDelete) {
            unset($node->children[$char]);
            return empty($node->children) && !$node->isEndOfWord;
        }
        return false;
    }

    // Count words
    public function countWords(): int {
        return $this->countWordsRec($this->root);
    }

    private function countWordsRec(TrieNode $node): int {
        $count = $node->isEndOfWord ? 1 : 0;
        foreach ($node->children as $child) {
            $count += $this->countWordsRec($child);
        }
        return $count;
    }
}

$trie = new Trie();
$trie->insert("cat");
$trie->insert("cats");
$trie->insert("dog");
$trie->insert("bat");

var_dump($trie->search("cat"));     // true
var_dump($trie->search("ca"));      // false (not a word)
var_dump($trie->startsWith("ca"));  // true
print_r($trie->autocomplete("ca")); // ["cat", "cats"]
echo $trie->countWords();           // 4

📊 Complexity

Insert	O(L)	L = word length
Search	O(L)	Independent of total words!
Prefix Search	O(L)	startsWith check
Delete	O(L)
Space	O(N*L)	N words × avg length (but shared prefixes save space)

🌍 Applications

Autocomplete / Typeahead: Google search suggestions
Spell Checker: Fast dictionary lookup
IP Routing: Longest prefix matching
Word Games: Boggle, Scrabble solver
Phone Directory: Contact search by prefix

💼 Interview Questions

Hash Table: O(1) average for exact search, but can't do prefix search. Trie: O(L) for all operations, naturally supports prefix queries and ordered traversal.

Store top K suggestions at each node during insert. Or: traverse from prefix node and collect all words via DFS/BFS. For large datasets, store only most frequent suggestions per node.

📝 Quick Quiz

Previous: Heap Next: Graph