TrieNode Class: Insert and Search
Build a TrieNode with children dict and is_end flag, implement insert and exact-search, and analyse O(m) time per operation where m is word length.
What Is a Trie?
A Trie (prefix tree) is a tree-shaped data structure where each node represents a character. Words are stored by chaining characters from root to leaf. The root represents an empty string. Each path from root to an is_end = True node spells out a stored word. Tries are ideal for prefix-based queries like autocomplete, spell-check, and IP routing, outperforming hash maps for these use cases.
TrieNode Class Design
A TrieNode has two fields: children — a dictionary mapping characters to child TrieNodes — and is_end — a boolean marking whether this node is the end of a stored word. Using a dictionary (instead of a fixed 26-char array) generalises to any character set and saves memory for sparse tries. Each node in the trie represents exactly one character position in the words below it.
class TrieNode:
def __init__(self):
self.children = {} # char -> TrieNode
self.is_end = False # True if a word ends here
class Trie:
def __init__(self):
self.root = TrieNode()
def __repr__(self):
return f'Trie(root with {len(self.root.children)} children)'
t = Trie()
print(t) # Trie(root with 0 children)All lessons in this course
- TrieNode Class: Insert and Search
- Prefix Search and Starts-With
- Wildcard and Regex Search in a Trie
- Word Search II: Trie + Backtracking on Grid