Designing an autocomplete system using a trie
A trie is a particular tree data structure that makes it possible for us to store prefixed data. As you descend a trie, you construct prefixes. As such, a node's children share a common prefix, which is the one we constructed so far while descending the tree. In fact, tries are like automaton, where descending a branch is analogous to consuming a transition literal and the state you'd get into when you do so is the prefix of that target node.
Generally, nodes of a trie carry information about the transitions and can carry weight depending on their use.
One interesting application of tries is text autocompletion. You can store strings in a prefixed manner in a trie. These strings would span over the shared portions of the tree, which represent the part that is common to them and which are forked when they become different. An autocomplete system would then work by descending the tree as far as the text you'd feed it goes and then...
