What is the most effective way to implement a trie in code?

A trie, also known as a prefix tree, is a data structure that stores strings in a hierarchical way, allowing fast and efficient search, insertion, and deletion operations. A trie consists of nodes that represent characters, and each node can have multiple children that share a common prefix. A trie can be used for various applications, such as autocomplete, spell check, word search, and pattern matching. In this article, you will learn what is the most effective way to implement a trie in code, using Python as an example.

1 Basic structure

The basic structure of a trie is a class that has two attributes: a value and a dictionary of children. The value is the character that the node represents, and the dictionary maps each child node's value to the child node itself. The root node has an empty value, and a special character, such as '*', is used to mark the end of a word. Here is an example of how to define a trie node class in Python:

class TrieNode:
  def __init__(self, value):
    self.value = value
    self.children = {}

Add your perspective

VIKAS TRIPATHI

🚀 SDE2@ Amazon || GCP Tester@ GoogleCloud || AWS Certified || ML Enthusiast || Agile Scrum Enthusiast || Let's Innovate Together! 🚀
Report contribution
The most effective way to implement a trie in code is to use a node-based approach where each node represents a character in the trie's keys, and the nodes are linked together to form the trie structure.

Like
Corrie Stoddard

Software Engineer
(edited)
Report contribution
You can add a boolean flag (eg "self.isEnd") to the trie node to represent whether or not it is the end of a word (as an alternative to the implementation below). For instance, this value would be false for the prefix "ca" but true for "cat". You can also add other properties depending on your specific use case, such as the frequency of the word or its parent.

Like

2 Insertion operation

To insert a word into a trie, you need to start from the root node and traverse the trie according to the characters of the word. For each character, you need to check if the current node has a child with that value. If yes, you move to that child node and continue. If no, you create a new child node with that value and add it to the current node's children dictionary. After you reach the end of the word, you add a '*' node as a child of the last node to indicate that the word is complete. Here is an example of how to implement a trie insertion method in Python:

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(char)
      current = current.children[char]
    current.children['*'] = TrieNode('*')

Add your perspective

Corrie Stoddard

Software Engineer
Report contribution
The slowest operation is the initial construction of the trie, which requires inserting all of the available words. This takes O(NL) (N = number of words, L = length of word) time. However, once built, any subsequent additions (and searches) can be done in only O(L).

Like

3 Search operation

To search for a word in a trie, you need to follow a similar logic as the insertion operation. You start from the root node and traverse the trie according to the characters of the word. For each character, you need to check if the current node has a child with that value. If yes, you move to that child node and continue. If no, you return False, as the word is not in the trie. After you reach the end of the word, you need to check if the current node has a '*' child, which means that the word is complete and in the trie. If yes, you return True. If no, you return False, as the word is only a prefix of another word in the trie. Here is an example of how to implement a trie search method in Python:

class Trie:
  # ... previous methods ...
  def search(self, word):
    current = self.root
    for char in word:
      if char not in current.children:
        return False
      current = current.children[char]
    return '*' in current.children

Add your perspective

Arnav Andrew J.

DevOps at Meesho
Report contribution
The code is correct. If we are talking about performance, we will have to perhaps use a separate data structure than the default python hashmap (dictionary) based on the size of the trie. In case of a small number of children of each node, an array (list) might actually perform better because of cache locality. As always in matters of performance, profile your code to see the hotspots. You might write code in a compiled language like C and use that as a python module as well (for example)

Like

4 Deletion operation

To delete a word from a trie, you need to use a recursive approach that removes the nodes that are not shared by any other words. You start from the root node and traverse the trie according to the characters of the word. For each character, you need to check if the current node has a child with that value. If yes, you move to that child node and continue. If no, you return False, as the word is not in the trie. After you reach the end of the word, you need to check if the current node has a '*' child, which means that the word is complete and in the trie. If yes, you delete the '*' child and return True. If no, you return False, as the word is only a prefix of another word in the trie. Then, you need to backtrack from the last node to the root node, and delete any node that has no other children. Here is an example of how to implement a trie deletion method in Python:

class Trie:
  # ... previous methods ...
  def delete(self, word):
    return self._delete(self.root, word, 0)
  def _delete(self, node, word, index):
    if index == len(word):
      if '*' in node.children:
        del node.children['*']
        return True
      else:
        return False
    else:
      char = word[index]
      if char not in node.children:
        return False
      else:
        child = node.children[char]
        deleted = self._delete(child, word, index + 1)
        if deleted and len(child.children) == 0:
          del node.children[char]
        return deleted

Add your perspective

5 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?

Add your perspective

Akash Rai

Data Engineer | Navigating the Complexities of Structured and Unstructured Data | Crafting Efficiency in Every Byte
Report contribution
One of the main aspect of the implementation is to validate the structure. Thoroughly test the Trie implementation for correctness and efficiency. Include tests for edge cases, such as empty strings, repeated insertions, and deletions. Consider performance testing to ensure scalability with large datasets. This data structure is valuable in various applications, ranging from dictionary implementations to autocomplete features in search engines. Careful consideration of factors like memory usage, time complexity, and ease of use will result in a Trie implementation that meets the specific needs of your project.

Like
Corrie Stoddard

Software Engineer
Report contribution
Tries can be used to efficiently implement autocomplete functionality. After the initial construction, you can search in O(L) time (L = length of word). This is much faster than alternative data structures whose time complexity depends on all of the words they contain, not just the word being searched for.

Like
Dhara Kumari Rajput 🧿

👩💻 Sr. Software Engineer Habib Bank AG Zurich | 🚀 Full Stack Solutions Expert | 🚀 Java | 🚀 Javascript | 🚀 React | 🚀 Node | 🚀 WordPress | 🚀 Shopify | 🚀 Funnelish | 🚀Tech Consultant
Report contribution
When implementing a trie, it's important to consider the trade-off between time complexity and space complexity. A trie can provide efficient search times at the cost of higher memory usage. To optimize a trie's performance, consider using a hash map to store child nodes in each trie node, which can lead to constant time insertions and searches. Additionally, consider the use cases: tries are excellent for autocomplete systems and spell checkers due to their prefix-based lookup capabilities. Keep in mind that real-world applications may require handling memory constraints and optimizing for both speed and space.

Like

What is the most effective way to implement a trie in code?

1

2

3

4

5

1 Basic structure

2 Insertion operation

3 Search operation

4 Deletion operation

5 Here’s what else to consider

Programming

Rate this article

Thanks for your feedback

More articles on Programming

More relevant reading

What is the most effective way to implement a trie in code?

1

2

3

4

5

1 Basic structure

2 Insertion operation

3 Search operation

4 Deletion operation

5 Here’s what else to consider

Programming

Rate this article

Thanks for your feedback

Explore Other Skills