Trie Data Structure: Complete Guide to Prefix Trees

What is the trie data structure?

A trie (pronounced “try”) is a tree-based data structure that stores strings efficiently by sharing common prefixes. Also called a prefix tree, a trie enables fast string search, insertion, and deletion operations in O(L) time, where L is the string length.

In a trie:

• Each node represents a single character.
• The path from the root to any node forms a prefix of one or more strings.
• Words that share prefixes use shared paths, making the structure space-efficient.
• We mark the end of a complete word using a special flag.

Let’s visualize this with an example. Consider the following strings:

• GAS
• GARLIC
• GLOBE
• GLOW
• JAZZ
• JANE
• JOKE
• PASS
• PASSIVE
• PALE
• PORT
• POKE

These can be stored in a trie like this:

In this image:

• All words originate from the root (denoted by *).
• Characters branch out, and shared prefixes like "PA" or "GL" are reused.
• For example, "PASS" is a prefix for "PASSIVE", so it doesn’t duplicate nodes.
• Red-circled nodes indicate the end of valid words in the trie.

This structure saves memory and makes prefix-based search and autocomplete operations very efficient.

Now that we understand how a trie is structured and how it stores words efficiently, let’s explore how to insert a string into a trie.

How to insert a string into a trie

To insert a string into a trie, we start at the root and follow the characters of the string one by one. If a character path already exists, we move forward. If not, we create a new node. Once all characters are inserted, we mark the end of the word.

Here’s a Python example showcasing the insertion of a string into a trie:

class TrieNode:
  def __init__(self):
    self.children = {}
    self.is_end_of_word = False

class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        current.children[char] = TrieNode()
      current = current.children[char]
    current.is_end_of_word = True

# Example usage
trie = Trie()
trie.insert("GLOBAL")

# Output check
node = trie.root
print("G" in node.children)   
print("L" in node.children["G"].children)

Copy to clipboard
Copy to clipboard

Here:

• TrieNode represents each letter node and stores its children (children) and whether it ends a word (is_end_of_word).

• Trie manages the structure, its insert() method adds each character step-by-step, creating nodes as needed and marking the final node as the end of the word.

The output for this code will be:

True 
True 

Copy to clipboard
Copy to clipboard

In the output:

• The first True confirms that the root node has a child 'G', the first letter of the inserted word "GLOBAL".

• The second True shows that the node for 'G' has a child 'L', the second letter in the word, meaning the path "G → L" exists in the trie.

How to search a string in a trie

When you want to check if a word exists in a trie, follow its characters from the root. The search is successful if all characters match and the last one is marked as the end of a word. Otherwise, the word either doesn’t exist or is just a prefix.

To search for a word in a trie, follow these steps:

• Start from the root and move character by character.
• If a character is missing at any point, return False.
• After the last character, check if the node marks the end of a word.

Here’s a Python implementation for the same:

class TrieNode:
  def __init__(self):
    self.children = {}
    self.is_end_of_word = False

class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        current.children[char] = TrieNode()
      current = current.children[char]
    current.is_end_of_word = True

  def search(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        return False
      current = current.children[char]
    return current.is_end_of_word

# Example usage
trie = Trie()
trie.insert("GLOBAL")

print(trie.search("GLOBE"))    
print(trie.search("GLOBES"))   

Copy to clipboard
Copy to clipboard

Here:

• The method starts at the root and goes through each character of the word.
• If a character isn’t present, it creates a new node for it.
• After all characters are added, the last node marks the end of the word.

The output of this code is:

False 
False 

Copy to clipboard
Copy to clipboard

"GLOBE" returns False as it’s only a prefix of "GLOBAL", while "GLOBES" returns False because only “GLOBAL” was inserted into the trie.

How to delete a word from a trie

Deleting a word from a trie must be done carefully since it might be a prefix of another word. The simplest way is to unset the is_end_of_word flag, which removes the word logically but retains the nodes, making it a good option when memory isn’t a concern. To free up memory, we need to remove the nodes not shared with any other word. This requires checking if the nodes have children or are marked as the end of another word, which are often handled using recursion.

Here’s a Python implementation to delete a word from a trie:

class TrieNode:
  def __init__(self):
    self.children = {}
    self.is_end_of_word = False

class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        current.children[char] = TrieNode()
      current = current.children[char]
    current.is_end_of_word = True

  def search(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        return False
      current = current.children[char]
    return current.is_end_of_word

  def delete(self, word):
    def _delete(node, word, depth):
      if depth == len(word):
        if not node.is_end_of_word:
          return False
        node.is_end_of_word = False
        return len(node.children) == 0

      char = word[depth]
      if char not in node.children:
        return False

      should_delete = _delete(node.children[char], word, depth + 1)

      if should_delete:
        del node.children[char]
        return not node.is_end_of_word and len(node.children) == 0

      return False

    _delete(self.root, word, 0)

# Example usage
trie = Trie()
trie.insert("JOKE")
trie.insert("JOKER")
trie.delete("JOKE")

print(trie.search("JOKE"))
print(trie.search("JOKER"))

Copy to clipboard
Copy to clipboard

Here:

• The delete() method uses a recursive helper _delete() to go through each character of the word.

• When it reaches the end, it unmarks is_end_of_word and checks if nodes can be safely removed (i.e., no children and not part of another word).

• As recursion unwinds, it deletes unused nodes, but keeps any node that is still part of another word.

The output this code generates is:

False 
True 

Copy to clipboard
Copy to clipboard

The output is False for "JOKE" because it was deleted by unmarking its end-of-word flag. It’s True for "JOKER" since the shared prefix wasn’t removed, and the word still exists in the trie.

Real-world applications of tries

Tries are widely used in software systems that involve text processing, search, and prediction. Their structure allows for fast lookups and efficient storage of words by sharing common prefixes, making them ideal for applications involving large dictionaries or real-time suggestions.

Some of the common use cases of tries are:

• Autocomplete systems: As you type in a search bar or messaging app, tries help suggest words by matching prefixes quickly.

• Spell checkers: Word processors use tries to check if a word exists; if not, they suggest the closest matching word.

• Dictionary storage: Tries efficiently store massive sets of words by collapsing shared prefixes.

• IP routing (with binary tries): Used in networking for quick lookup of routing prefixes.

• Word games and puzzles: Tries help validate moves and suggest possible words based on a given prefix.

These examples show how tries power many features we rely on daily, making them a fundamental tool in efficient text-based processing.

Conclusion

In this article, we explored the trie which is a powerful tree-based data structure designed for efficient string storage and retrieval. We learned how tries work, how to insert, search, and delete words, and where they’re used in real-world applications like autocomplete and spell-checking.

If you’re interested in implementing more advanced data structures or improving your coding skills, check out Codecademy’s Learn Data Structures and Algorithms course to build a deeper foundation and practice concepts like tries with hands-on projects.

Frequently asked questions

1. Why are there 26 references in Tries?

A trie often uses 26 references (or child pointers) per node when dealing with the English alphabet, one for each letter (A–Z). This allows constant-time access to any character during insertion or search, assuming only lowercase or uppercase letters are used.

2. When should I use Tries?

Use tries when you need fast prefix-based lookups, such as autocomplete, spell-checking, or implementing dictionaries. Tries are especially useful when you have a large set of strings and want efficient retrieval based on prefixes.

3. Why is a trie better than a hashmap?

While hashmaps offer fast exact lookups, tries are better for prefix-based searches and memory optimization when storing many strings with shared prefixes. Tries also preserve lexicographical order, which hashmaps do not.

4. What is the use of a trie in Blockchain?

In blockchain, a variant called a Merkle Patricia Trie is used to store state data. It allows efficient verification and retrieval of transactions, balances, and contracts, helping ensure data integrity and fast synchronization across nodes.