Python Program to Implement Trie Data Structure

A Python trie can be implemented by creating a TrieNode class with children dictionary and end-of-word flag, and a Trie class with insert(word) and search(word) methods to add and find words.

Examples

InputInsert: 'cat', Search: 'cat'

OutputTrue

InputInsert: 'dog', Search: 'do'

OutputFalse

InputInsert: 'apple', Search: 'apple'

OutputTrue

How to Think About It

To build a trie, think of it as a tree where each node holds letters. When inserting a word, you add nodes for each letter if they don't exist. Searching means following nodes for each letter; if you reach the end and the word is marked complete, it exists.

Algorithm

1

Create a root node with empty children and end-of-word flag false.

2

For inserting a word, start at root and for each letter, create a child node if missing, then move to that child.

3

After the last letter, mark the node as end-of-word true.

4

For searching, start at root and follow child nodes for each letter.

5

If any letter node is missing, return false.

6

If all letters found and end-of-word is true, return true; else false.

Code

python

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

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

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

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

# Example usage
trie = Trie()
trie.insert('cat')
print(trie.search('cat'))  # True
print(trie.search('ca'))   # False
trie.insert('car')
print(trie.search('car'))  # True

Output

True
False
True

Dry Run

Let's trace inserting 'cat' and searching 'cat' and 'ca' through the trie.

1

Insert 'cat'

Start at root node. For 'c', no child, create node. For 'a', no child, create node. For 't', no child, create node. Mark 't' node as end-of-word True.

2

Search 'cat'

Start at root. Find 'c' child, then 'a' child, then 't' child. 't' node is end-of-word True, so return True.

3

Search 'ca'

Start at root. Find 'c' child, then 'a' child. 'a' node is not end-of-word, so return False.

Operation	Current Node Children	Is End of Word
Insert 'c'	{'c': TrieNode}	False
Insert 'a'	{'a': TrieNode}	False
Insert 't'	{'t': TrieNode}	True
Search 'c'	{'c': TrieNode}	False
Search 'a'	{'a': TrieNode}	False
Search 't'	{}	True

Why This Works

Step 1: TrieNode holds children and end flag

Each TrieNode stores a dictionary of children nodes for letters and a boolean is_end to mark if a word ends here.

Step 2: Insert adds nodes for letters

When inserting, we create nodes for letters not present and move down the trie, marking the last node as end-of-word.

Step 3: Search follows nodes to check word

Searching means moving through nodes for each letter; if any letter is missing or last node is not end-of-word, the word is not found.

Alternative Approaches

Using defaultdict for children

python

from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.is_end = False

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

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.children[char]
        node.is_end = True

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

trie = Trie()
trie.insert('dog')
print(trie.search('dog'))  # True
print(trie.search('do'))   # False

Using defaultdict simplifies child node creation but may create nodes unintentionally during search if not careful.

Using nested dictionaries only

python

class Trie:
    def __init__(self):
        self.root = {}
        self.end_symbol = '*'

    def insert(self, word):
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_symbol] = True

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

trie = Trie()
trie.insert('apple')
print(trie.search('apple'))  # True
print(trie.search('app'))    # False

This approach uses only dictionaries without classes, making it simpler but less object-oriented.

Complexity: O(m) time, O(m) space

Time Complexity

Insertion and search both take O(m) time where m is the length of the word, because each letter is processed once.

Space Complexity

Space is O(m) for each inserted word in the worst case, as new nodes are created for letters not already in the trie.

Which Approach is Fastest?

All approaches have similar time complexity; using defaultdict can simplify code but may use slightly more memory.

Approach	Time	Space	Best For
Class-based TrieNode	O(m)	O(m)	Clear structure and easy to extend
defaultdict children	O(m)	O(m)	Simpler code but watch for unintended nodes
Nested dictionaries only	O(m)	O(m)	Minimal code, less object-oriented