DSA Interview Prep · Lesson

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.

TrieNode Class: Insert and Search is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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)

Insert Operation

To insert a word, traverse from the root, creating a new TrieNode for each character that doesn't already exist in the current node's children. After processing all characters, set is_end = True on the final node. Inserting 'apple' and 'app' creates the chain a→p→p→l→e (is_end=True for 'apple'), with the p at position 3 also marked is_end=True for 'app'.

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

t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)

Search Operation

To search for an exact word, traverse the trie following each character. If any character is missing from the current node's children, return False. If all characters are found, return node.is_end — True only if a word ends exactly here (not just a prefix). This distinction between 'prefix exists' and 'exact word exists' is critical and often tested.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end  # must be a complete word

t = Trie()
t.insert('apple')
print(t.search('apple'))   # True
print(t.search('app'))     # False (app not inserted)
print(t.search('orange'))  # False

Starts-With (Prefix Search)

The starts_with method checks if any inserted word has the given prefix. It follows the same traversal as search, but instead of checking is_end, it returns True as soon as all prefix characters are successfully followed — meaning the prefix path exists in the trie.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True  # prefix path exists

t = Trie()
t.insert('apple')
print(t.starts_with('app'))   # True
print(t.starts_with('ape'))   # False
print(t.search('app'))         # False (not inserted)

Time and Space Complexity

Each trie operation (insert, search, starts_with) takes O(m) time where m is the word length — we traverse at most m nodes. Space: O(ALPHABET_SIZE × N × M) where N is the number of words and M is the average word length. In practice, shared prefixes reduce space significantly. A hash-map-based children dict uses less space than a fixed 26-char array for sparse tries, at the cost of slightly higher constant overhead per lookup.

Using an Array Instead of Dict

For lowercase English letters only, use a fixed-size array children = [None] * 26 with index ord(c) - ord('a'). This is faster (O(1) child lookup vs hash map) and has predictable memory layout. Use the dict version when the character set is large or unknown (e.g., Unicode), and the array version for competition-style problems with only lowercase letters.

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNodeArray()
    
    def insert(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNodeArray()
            node = node.children[idx]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None: return False
            node = node.children[idx]
        return node.is_end

t = TrieArray()
t.insert('cat')
print(t.search('cat'))  # True
print(t.search('car'))  # False

Delete Operation

Deletion from a trie must handle three cases: (1) word not present — do nothing; (2) word present but is a prefix of another word — only unset is_end; (3) word present and not a prefix — delete nodes bottom-up, stopping when a node has other children or is another word's end. Deletion is rarely tested in interviews but good to know conceptually.

Counting Words with Prefix

Augment each node with a count field incremented on every insert pass-through. To count words with a given prefix, traverse to the prefix's end node and return its count. This enables O(m) autocomplete queries without traversing all children — a useful extension for real-world autocomplete systems.

class TrieNodeCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # words passing through this node

class TrieCount:
    def __init__(self):
        self.root = TrieNodeCount()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNodeCount()
            node = node.children[c]
            node.count += 1  # increment on each level
        node.is_end = True
    
    def count_with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return 0
            node = node.children[c]
        return node.count

t = TrieCount()
for w in ['apple','app','application','apply']:
    t.insert(w)
print(t.count_with_prefix('app'))   # 4
print(t.count_with_prefix('appl'))  # 3

Trie vs Hash Map Comparison

A hash map can do exact lookup in O(m) average time but cannot efficiently answer prefix queries (requires scanning all keys). A Trie answers prefix queries in O(p) where p is prefix length, naturally groups words by shared prefixes, and does not need hashing. Use a trie when: frequent prefix queries, autocomplete, spell-check. Use a hash map when: only exact lookups needed.

Tries in Real-World Systems

Real-world trie uses include: autocomplete (Google search suggestions), spell checkers (finding closest matching words), IP routing (longest prefix matching in routers), T9 predictive text (character disambiguation), and DNS resolvers (hierarchical domain name lookup). In each case, the trie's O(m) per-operation and O(ALPHABET × nodes) space trade-off makes it the right tool for fast, prefix-aware lookups at scale.

Quick Check

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

Lesson Recap

In this lesson you learned: a TrieNode has a children dict and is_end boolean, insert traverses character by character creating nodes as needed and sets is_end at the end, and search checks is_end while starts_with only checks if the prefix path exists. Next up we add prefix-based autocomplete and the starts_with method in more depth.

Frequently asked questions

Is the “TrieNode Class: Insert and Search” lesson free?

Yes — the full text of “TrieNode Class: Insert and Search” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “TrieNode Class: Insert and Search” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

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

← Back to DSA Interview Prep