Notes on Tries

A trie is a tree-like structure for storing a set of strings. It’s also called a prefix tree. For example, given the strings apple, app, apricot, and banana, the trie would look like this:

A basic implementation consists of the TrieNode class and the Trie class. For former is a node with a dictionary of children nodes and an indicator of whether the node is the end of a word. The latter is a class with a single root node and methods for inserting and searching for words.

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


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

    def add_word(self, w: str):
        # Start at the root, will be updated as we go
        node = self.root

        # For each character in the word
        for c in w:
            if c not in node.children:
                # we haven't seen this character before, so add it
                node.children[c] = TrieNode()

            # move to the next node
            node = node.children[c]

        # mark the end of the word after the last character
        node.is_end_of_word = True

    def search(self, w: str) -> bool:
        # Start at the root, will be updated as we go
        node = self.root
        for c in w:
            # as soon as we can't find a character, the word isn't in the trie
            if c not in node.children:
                return False
            node = node.children[c]

        # if we've reached the end of the word, it's in the trie if
        # the node is marked as the end of a word
        return node.is_end_of_word

Complexity

Inserting, searching, and deleting words in a trie is \(O(m)\) where \(m\) is the length of the word. This is because we only need to traverse the length of the word to insert, search, or delete it, which is much faster than if we had to search through all the words individually.

The space complexity of the trie is \(O(n * \overline{w})\) where \(n\) is the number of words and \(\overline{w}\) is the average length of the words. This is because each node in the trie has a dictionary of children nodes, which can be up to the size of the alphabet. If the average length of the words is \(\overline{w}\), then the number of nodes in the trie is \(n * \overline{w}\).