Tries/Practice/Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) - Explained Visually

mediumTime: O(m) per opSpace: O(n * m)

Each node is a dictionary of children plus an end-of-word flag. To insert or search, walk one character at a time, creating nodes that do not exist. Search succeeds only at nodes whose end flag is set; a prefix just has to exist as a path.

Why it works

Words that share prefixes share nodes, so storage is bounded by total characters, not total words. Every operation touches at most one node per character - O(m) for a word of length m - which is why autocomplete and spell-checkers are built on tries.

The problem

Implement a Trie with insert(word), search(word) (returns true if word exists), and startsWith(prefix) (returns true if any word has this prefix) methods.

Hints

  • Each TrieNode needs a children dict mapping char -> TrieNode.
  • Mark the last node of each inserted word with is_end = True.
  • search requires is_end == True at the end; starts_with just needs the path to exist.

Test cases

InputExpected
search after insert("apple")True
search("app") before insert("app")False
starts_with("app")True

Reference starter code

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

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

    def insert(self, word):
        pass

    def search(self, word):
        pass

    def starts_with(self, prefix):
        pass

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

Try it yourself

Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.

Studying Tries but not ready to grind? Get the 30-day plan by email.
One email with the study plan. No spam, unsubscribe anytime.