Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) is the canonical "build a data structure" interview question. A trie stores a set of strings as a tree of characters, with shared prefixes folded together — which makes prefix queries blazingly fast.

The slow way first

You could store every word in a list and, for each query, scan the whole list. search is a membership check, but startsWith would compare the prefix against every word — O(n · L) for n words of length L. With millions of words (an autocomplete index) that is hopeless.

The question to ask: what do these words share? Words with the same prefix share a path. If we store characters in a tree, every word that starts with "ap" walks the same first two nodes — so a prefix query is just one walk down the tree, independent of how many words exist.

The idea: one node per character, prefixes shared

Build a tree where each node has a children dictionary mapping a character to the next node, plus an is_end boolean. The root is the empty prefix. To insert a word, walk it character by character, creating a child node only when one does not already exist. At the final node, set is_end = True to record that a real word ends here.

The crucial distinction: a node existing on the path means a prefix exists, but only is_end = True means a full word ends there. That single flag is what makes search and startsWith different.

Walk through it

Step through the animation. Inserting "app" creates three nodes down a path and flags the last "p" as is_end. Inserting "apple" reuses a → p → p (they already exist) and only creates "l" and "e". Then watch the queries: search("app") lands on a flagged node (True); search("ap") lands on a node whose flag is False (False); startsWith("ap") just confirms the path exists (True).

Pseudocode

insert(word):
    node = root
    for ch in word:
        if ch not a child of node:
            create a new node as node.children[ch]
        node = node.children[ch]
    node.is_end = True
 
search(word):    walk the path; return node.is_end if it exists, else False
startsWith(pre): walk the path; return True if it exists, else False

The Python solution

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True
 
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end
 
    def startsWith(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

• Each TrieNode carries a children dict (character → next node) and an is_end flag — that is the whole structure.
• insert walks the word, lazily creating a child only when it is missing, then flags the last node with is_end = True.
• search and startsWith share the same walk. The only difference is the last line: search returns node.is_end; startsWith returns True once the path is found.
• If a character is missing mid-walk, both queries bail out early with False.

Complexity

Every operation is O(L) — it depends only on the length of the string you pass in, not on how many words the trie holds. That is exactly why tries power autocomplete and spell-checkers.

When this pattern shows up

Practice