Trie Data Structure for Prefix Search and Autocomplete

A trie (prefix tree) stores strings as branching paths of single characters. Each node holds a map of characters to child nodes and a boolean that marks whether the node terminates a complete word. Inserting a word walks one character at a time, creating nodes as needed and marking the final one. Searching checks whether the walk completes at a marked end node. startsWith() just checks that the walk reaches any node at all.

The autocomplete() method walks to the prefix node, then does a recursive depth-first traversal of the subtree, collecting every word it finds along the way. Results are sorted alphabetically before returning. Lookup and insertion are both O(m) where m is the word length, independent of how many words are stored.

<?php

/**
 * Trie (prefix tree): O(m) insert and search where m = word length.
 * Useful for autocomplete, spell checking, IP routing tables.
 */
class TrieNode
{
    public array $children = [];
    public bool  $isEnd    = false;
}

class Trie
{
    private TrieNode $root;

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

    public function insert(string $word): void
    {
        $node = $this->root;
        foreach (str_split($word) as $char) {
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEnd = true;
    }

    public function search(string $word): bool
    {
        $node = $this->findNode($word);
        return $node !== null && $node->isEnd;
    }

    public function startsWith(string $prefix): bool
    {
        return $this->findNode($prefix) !== null;
    }

    public function autocomplete(string $prefix): array
    {
        $node = $this->findNode($prefix);
        if ($node === null) return [];

        $results = [];
        $this->collect($node, $prefix, $results);
        sort($results);
        return $results;
    }

    private function findNode(string $prefix): ?TrieNode
    {
        $node = $this->root;
        foreach (str_split($prefix) as $char) {
            if (!isset($node->children[$char])) return null;
            $node = $node->children[$char];
        }
        return $node;
    }

    private function collect(TrieNode $node, string $current, array &$results): void
    {
        if ($node->isEnd) $results[] = $current;
        foreach ($node->children as $char => $child) {
            $this->collect($child, $current . $char, $results);
        }
    }
}

// Demo
$trie = new Trie();
$words = ['apple', 'app', 'application', 'apply', 'apt', 'banana', 'band', 'bandwidth', 'php', 'phpunit', 'phpdoc'];

foreach ($words as $w) $trie->insert($w);

var_dump($trie->search('app'));         // true
var_dump($trie->search('ap'));          // false (not inserted)
var_dump($trie->startsWith('ap'));      // true

echo "\nAutocomplete 'app': ";
print_r($trie->autocomplete('app'));    // app, apple, application, apply

echo "\nAutocomplete 'ban': ";
print_r($trie->autocomplete('ban'));    // banana, band, bandwidth

echo "Autocomplete 'xyz': ";
print_r($trie->autocomplete('xyz'));    // []