Introduction to Trie

Let’s go over the Trie pattern, its real-world applications, and some problems we can solve with it.

We'll cover the following

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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.