How to Implement Trie in Python: Simple Guide with Example

To implement a trie in Python, create a class with nodes that store children in a dictionary and a flag for word endings. Insert words by adding characters as keys in children dictionaries, and search by traversing these keys.

Syntax

A trie is built using nodes where each node contains:

• children: a dictionary mapping characters to child nodes
• is_end_of_word: a boolean flag marking if a node completes a word

Basic methods include insert(word) to add words and search(word) to check if a word exists.

python

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: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

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

Example

This example shows how to create a trie, insert words, and search for them.

python

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: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

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

# Create trie and insert words
trie = Trie()
trie.insert("apple")
trie.insert("app")

# Search words
print(trie.search("apple"))  # True
print(trie.search("app"))    # True
print(trie.search("appl"))   # False
print(trie.search("banana")) # False

Output

True
True
False
False

Common Pitfalls

Common mistakes when implementing tries include:

• Not marking the end of a word, causing search to give wrong results.
• Using lists instead of dictionaries for children, which slows down lookups.
• Not handling empty strings or invalid inputs.

Always ensure is_end_of_word is set correctly after insertion.

python

class TrieNode:
    def __init__(self):
        self.children = []  # Wrong: list instead of dict
        self.is_end_of_word = False

# Correct way uses dict for fast lookup
class TrieNodeCorrect:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

Quick Reference

• Insert: Traverse or create nodes for each character, mark last node as word end.
• Search: Traverse nodes for each character, return true only if last node marks word end.
• Children: Use dictionary for O(1) character lookup.
• Edge cases: Handle empty strings and non-alphabetic characters as needed.

Key Takeaways

Use a dictionary in each node to map characters to child nodes for fast access.

Mark the end of a word with a boolean flag to distinguish complete words from prefixes.

Insert words by creating nodes for each character if they don't exist.

Search by traversing nodes and checking the end-of-word flag.

Avoid using lists for children to prevent slow lookups and bugs.