How to implement trie in C++

Trie, also known as prefix tree, is an elegant and efficient data structure to use as a symbol table for keys that are strings. In a trie, the number of accesses required to search or insert a string is linear in the string length. In fact, it is just one more than the number of characters in the string.

Sedgewick’s Algorithms textbook has a particularly elegant trie implementation in Java. I created a similar C++ version just for fun here: