Introduction to Trie

About the pattern

A trie is a tree data structure used for storing and locating keys from a set. The keys are usually strings that are stored character by character—each node of a trie corresponds to a single character rather than the entire key.

Below are the key characteristics of a trie:

• The order of characters in a string is represented by edges between the adjacent nodes. For example, in the string “are”, there will be an edge from node a to node r to node e. That is, node a will be the parent of node r, and node r will be the parent of node e.

• The level of nodes signifies the position of characters within a word. Each level corresponds to a specific index in the word being represented. In other words, at any given level, each node corresponds to a distinct character in the words stored in the trie. As we traverse down the trie from the root to a leaf node, the characters encountered along the path collectively form the word associated with that path.

• It contains end-of-word nodes that mark the conclusion of a word within the trie structure. Each end-of-word node signifies the termination point of a word stored in the trie. This characteristic is crucial for efficient word retrieval and validation operations, as it allows the trie to distinguish between prefixes and complete words during searches or insertions.

The following illustration will help you understand how the strings are stored:

This way, additional space is not required for storing strings with common prefixes. We can keep moving down the tree until a new character that’s not present in the node’s children is encountered and add it as a new node. Similarly, searches can also be performed using depth-first search by following the edges between the nodes. Essentially, in a trie, words with the same prefix or stem share the memory area that corresponds to the prefix.

Below is an explanation of ...