A Trie in PHP

A trie is a tree used to compactly represent a natural-language dictionary. The nodes themselves contain only a part of the information they represent: the node’s value must be appended to its parent’s key in order to obtain the information it represents. Most nodes in a trie (in some tries, all nodes) contain a single character. A node’s children contain characters which may be appended to its key in order to form a word in the dictionary.

That description is probably better if you already understand what a trie is supposed to do. A picture works better.

A trie representing the words 'cart,' 'care,' 'cat' and 'coins'

A trie storing the words ‘cart,’ ‘care,’ ‘cat’ and ‘coins’

The trie above could just as well store ‘car,’ as well, so long as we give each node a flag to determine whether its key is a word in our dictionary.

Here’s the code for the trie and the trienode:

And the code to try it out:

Which gives the expected output.