LeetCode 208 · Tries

Implement Trie (Prefix Tree), explained with a picture

A letter tree that grows as words are added.

MediumTries
▶ Watch it step by step

The problem

Implement a Trie (prefix tree) with insert(word), search(word) (is that exact word stored?) and startsWith(prefix) (does any stored word start with it?).

Input:  insert apple, search apple, search app, startsWith app, insert app, search app
Output: true, false, true, true

Picture it

Picture a letter tree. Each step down a branch is one letter, so words that start the same way share the same branch (“app” and “apple” share a-p-p). A node gets a special end mark when a whole word finishes there. Searching just walks down the letters; if a letter branch is missing, the word isn’t there.

How to recognise it

  • You store many strings and must answer prefix questions: "does any word start with this?", "list the words that start with this", autocomplete.
  • Words share beginnings (app, apple, apply), so storing each shared beginning once saves both space and work.
  • Each query should cost time proportional to the length of the query, not the number of stored words.
  • A trie (prefix tree) is a tree where each edge is one letter and each path from the root spells a prefix. A marker on a node says "a whole word ends here".

Start with brute force

Keep the words in a set. Exact search is a set lookup; a prefix query checks every stored word.

class TrieBrute:
    def __init__(self):
        self.words = set()
    def insert(self, word):
        self.words.add(word)
    def search(self, word):
        return word in self.words
    def starts_with(self, prefix):
        return any(w.startswith(prefix) for w in self.words)

insert and search are O(L) for a word of length L (hashing reads every character). But starts_with is O(N · L) for N stored words. LeetCode allows 3 × 10^4 calls: 1.5 × 10^4 inserts followed by 1.5 × 10^4 prefix queries that miss is about 2.25 × 10^8 startswith checks.

From brute force to the idea

  1. Find the waste. A prefix query compares the prefix with every word, even words that differ in the first letter. And app, apple and apply each store the same app again.
  2. Share prefixes. Build a tree of nested dictionaries: self.root maps a first letter to a child dictionary, which maps the next letter to its child, and so on.
  3. Insert by walking and growing. For each letter, node.setdefault(ch, {}) follows the branch if it exists and creates it otherwise. At the end, node["$"] = True marks that a word ends here. The $ key cannot clash with a letter because words use only lowercase letters.
  4. Search by walking. Follow one letter at a time. A missing letter means no stored word has this prefix, so return False.
  5. One walk, two questions. After the walk, a prefix query is already satisfied (prefix or ...). An exact search also needs the $ marker, because app can be a path inside apple without being a stored word. starts_with simply calls search(prefix, prefix=True).

This is the key idea: follow the query one letter at a time down shared branches; the end node tells you whether it is a prefix, and its marker whether it is a word.

The key idea

Each node holds children by letter plus an end-of-word flag. Every operation costs O(length of the word).

Python solution

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})   # grow a branch if missing
        node["$"] = True                     # mark: a word ends here
    def search(self, word, prefix=False):
        node = self.root
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return prefix or "$" in node
    def starts_with(self, prefix):
        return self.search(prefix, prefix=True)

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceinsert and search O(L); starts_with O(N · L): every word is checkedO(total characters)
Dictionary trie (shown code)O(L) for every operation: one dictionary step per letterO(total characters) in the worst case, less when prefixes are shared; each node is a whole dictionary, so the constant is large

Edge cases

  • The example: after inserting apple, search("app") is False and starts_with("app") is True; after inserting app, search("app") is True.
  • Inserting a word twice: harmless; the path exists and the marker is set again.
  • Query longer than any word (search("apples")): the walk hits a missing s and returns False.
  • Empty prefix: starts_with("") returns True even on an empty trie, because the walk does nothing. Whether that is right depends on your definition; LeetCode never asks it.
  • Empty word: search("") is False unless "" was inserted, which marks the root.

Common mistakes

  • Forgetting the end marker and answering search with "did the walk succeed?". Then search("app") is True after inserting only apple.
  • Creating nodes during search (using setdefault there), which makes the trie grow on every miss.
  • Using a letter as the marker key or storing the marker as a child, so a word containing that character breaks.
  • Storing the whole word at every node "to make autocomplete easy", which turns the space cost from shared prefixes into O(L²) per word.
Your turn: count by prefix

Add count_prefix(prefix): how many inserted words start with the prefix (a word inserted twice counts twice). After inserting apple, app, apply, bat and apple again, count_prefix("app") is 4. Each call must stay O(L). Describe your approach, then write it if you like.

Compare with our answer

Store a counter in every node: how many inserted words passed through it. Increment along the path on each insert. A query walks to the prefix's node and reads its counter, so no subtree is explored.

class CountTrie:
    def __init__(self):
        self.root = {"#": 0}
    def insert(self, word):
        node = self.root
        node["#"] += 1
        for ch in word:
            node = node.setdefault(ch, {"#": 0})
            node["#"] += 1             # one more word passes through here
    def count_prefix(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node:
                return 0
            node = node[ch]
        return node["#"]

count_prefix("") is the total number of inserts. Both methods are O(L).

A strong answer mentions: updating the counter on every node of the path (including the root), why a missing letter returns 0, and why this beats walking the whole subtree.

Check what stuck

1. A search box must suggest stored product names that begin with what the user has typed so far. Which structure fits best?

2. Why does search("app") return False after inserting only apple?

3. A learner rewrites the last line of search as return "$" in node. After inserting apple, which call now gives a wrong answer?

Score 60% or more and the lesson is marked complete.