How to Implement a Trie Data Structure

A Trie is a tree-like data structure where each node represents a single character. Words are stored by chaining characters from the root down to a leaf. All words that share a common prefix share the same path from the root, making prefix-based searches extremely fast.

Each Trie node contains two things. First, an array or Hash Map of children where each slot corresponds to a possible next character. For lowercase English letters, this is an array of 26 slots. Second, a boolean flag called isEndOfWord that marks whether the path from root to this node spells a complete word.

To insert a word, start at the root and iterate through each character of the word. For each character, calculate its index and check if a child node exists at that index. If no child exists, create a new Trie node there. Move to the child node. After processing all characters, set the isEndOfWord flag of the last node to true.

To search for a complete word, start at the root and traverse one character at a time. For each character, check if the corresponding child node exists. If any child is missing, the word does not exist in the Trie, so return false. After processing all characters, return the isEndOfWord flag of the last node.

The prefix search is identical to the full word search except for the final step. Traverse the Trie character by character. If any child is missing, return false. If you successfully traverse all characters of the prefix, return true regardless of the isEndOfWord flag. The prefix exists in the Trie.

Every operation in a Trie, whether insert, search, or prefix check, runs in time proportional to the length of the word or prefix being processed. It does not depend on how many words are stored in the Trie. This makes Tries extremely efficient for large dictionaries.

Tries are used in autocomplete systems where you type a few letters and see suggestions. They are also used in spell checkers, IP routing tables, word games like Boggle, and any system that needs fast prefix lookups across a large collection of strings.