How to create a trie in Python

Mastering Tries: An Efficient Data Structure for String Operations in Python

Explore the concept of Tries (prefix trees), their applications, and learn how to implement them efficiently in Python for tasks like autocomplete and spell checking.

In computer science, a Trie, also known as a prefix tree or digital tree, is a tree-like data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated. All children of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Tries are particularly efficient for operations like prefix matching, autocomplete, and spell checking due to their ability to quickly traverse common prefixes.

Understanding the Trie Structure

A Trie is composed of nodes, where each node typically represents a character. The path from the root to a specific node forms a prefix. If a node marks the end of a valid word, it's often flagged as such. Each node can have multiple children, usually one for each possible character in the alphabet (e.g., 26 for lowercase English letters). This structure allows for very fast lookups and insertions of strings, proportional to the length of the string, not the number of strings in the Trie.

graph TD
    root["root"] --> A["a"]
    A --> P["p"]
    P --> P2["p"]
    P2 --> L["l"]
    L --> E["e (word)"]
    A --> N["n"]
    N --> T["t (word)"]
    root --> B["b"]
    B --> A2["a"]
    A2 --> T2["t (word)"]

    style E fill:#bbf,stroke:#333,stroke-width:2px
    style T fill:#bbf,stroke:#333,stroke-width:2px
    style T2 fill:#bbf,stroke:#333,stroke-width:2px

A simple Trie storing words 'apple', 'ant', and 'bat'. Nodes marked as '(word)' indicate the end of a valid word.

Implementing a Trie Node in Python

The fundamental building block of a Trie is the Trie Node. Each node needs to store references to its children (typically a dictionary mapping characters to child nodes) and a boolean flag indicating whether the node represents the end of a complete word. Let's define a simple TrieNode class.

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

    def __repr__(self):
        return f"TrieNode(children={list(self.children.keys())}, is_end_of_word={self.is_end_of_word})"

Basic implementation of a TrieNode class.

Building the Trie Class: Insertion and Search

With the TrieNode in place, we can now implement the Trie class itself. This class will manage the root node and provide methods for inserting words and searching for words or prefixes. The core logic involves traversing the Trie character by character, creating new nodes as needed during insertion, and checking for the is_end_of_word flag during search.

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

    def insert(self, word: str) -> None:
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                current_node.children[char] = TrieNode()
            current_node = current_node.children[char]
        current_node.is_end_of_word = True

    def search(self, word: str) -> bool:
        current_node = self.root
        for char in word:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return current_node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        current_node = self.root
        for char in prefix:
            if char not in current_node.children:
                return False
            current_node = current_node.children[char]
        return True

# Example Usage:
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("apricot")

print(f"Search 'apple': {trie.search('apple')}") # True
print(f"Search 'app': {trie.search('app')}")     # True
print(f"Search 'ap': {trie.search('ap')}")       # False (not a full word)
print(f"Search 'banana': {trie.search('banana')}") # False

print(f"Starts with 'app': {trie.starts_with('app')}") # True
print(f"Starts with 'ban': {trie.starts_with('ban')}") # False

Python Trie implementation with insert, search, and starts_with methods.

Advanced Trie Operations: Autocomplete

One of the most powerful applications of Tries is autocomplete. By traversing the Trie to the end of a given prefix, we can then perform a Depth-First Search (DFS) or Breadth-First Search (BFS) from that node to find all words that share that prefix. This is incredibly efficient for suggesting words as a user types.

class Trie:
    # ... (previous TrieNode and Trie __init__, insert, search, starts_with methods) ...

    def _find_words_from_node(self, node: TrieNode, current_prefix: str, results: list):
        if node.is_end_of_word:
            results.append(current_prefix)
        for char, child_node in node.children.items():
            self._find_words_from_node(child_node, current_prefix + char, results)

    def autocomplete(self, prefix: str) -> list[str]:
        current_node = self.root
        for char in prefix:
            if char not in current_node.children:
                return [] # No words start with this prefix
            current_node = current_node.children[char]
        
        results = []
        self._find_words_from_node(current_node, prefix, results)
        return results

# Example Usage:
trie = Trie()
trie.insert("apple")
trie.insert("app")
trie.insert("apricot")
trie.insert("apply")
trie.insert("banana")

print(f"Autocomplete 'ap': {trie.autocomplete('ap')}")
# Expected: ['app', 'apple', 'apply', 'apricot'] (order may vary based on dict iteration)
print(f"Autocomplete 'ban': {trie.autocomplete('ban')}")
# Expected: ['banana']
print(f"Autocomplete 'xyz': {trie.autocomplete('xyz')}")
# Expected: []

Adding an autocomplete method to the Trie class.