Implement Trie (Prefix Tree)

Table of Contents +

Type three letters into a search box and a list of words pops up instantly. How does it do that so fast? It does not scan a giant list of words every time. It walks a tree of letters. That tree is called a trie. This question asks you to build one from scratch.

🎯 The Problem

You have to build a data structure called a trie.

A trie is a tree where each node stands for one letter, and a path from the top spells a word.
People also call it a prefix tree, because words sharing a start prefix share the same path.
insert(word) adds a word.
search(word) returns true only if that exact word was added before.
startsWith(prefix) returns true if any added word begins with that prefix.

Operations:
  insert("apple")
  search("apple")    -> true
  search("app")      -> false   (we never inserted "app" as a full word)
  startsWith("app")  -> true    (some word begins with "app")
  insert("app")
  search("app")      -> true

Notice the gap between search and startsWith. A path can exist without being a full word. So each node carries a flag that says “a word ends here”.

Here is the trie after inserting “apple” and “app”. Each circle is a node holding one letter. The node marked END means a complete word stops there.

🐢 Approach 1: A List of Words (Brute Force)

The idea in one line: keep every word in a plain list and scan it on each query.

The idea:

insert pushes the word onto a list.
search scans the list for an exact match.
startsWith scans the list for any word that begins with the prefix.

How it works:

Every lookup walks the whole list of words.
For startsWith, test the start of each stored word one by one.

Why it is weak:

Each lookup depends on how many words you stored, not the word length.
With many words each query gets slow.
A search box that reacts to every keystroke cannot afford this.

Here is the list-of-words code:

class Trie:
    def __init__(self):
        self.words = []

    def insert(self, word):
        self.words.append(word)

    def search(self, word):
        return word in self.words

    def startsWith(self, prefix):
        return any(word.startswith(prefix) for word in self.words)

⚡ Approach 2: A Tree of Letters (Best)

The idea in one line: store words as paths of letters so shared prefixes share one path.

The idea:

Words that start the same way walk the same path. “apple” and “app” both follow a, p, p.
Each node holds a map from a letter to its child node.
Each node also holds a boolean isEnd, true when a full word finishes here.

How each operation works:

insert: start at the root, walk each letter, create a child when missing, set isEnd on the last node.
search: walk the same path. A missing child means not found. At the end, return that node’s isEnd.
startsWith: walk the prefix. Ignore isEnd. If the whole path exists, return true.

Why it is fast:

Every operation takes time equal to the word length, not the number of words.
A five-letter word takes about five steps no matter how many words you stored.

Here is how insert and search walk the same path for “app”. Each step moves to a child node.

Steps to Solve

Make a node type that holds a map of children (letter to node) and a boolean isEnd.
For insert, start at the root and walk each letter. Create a child when it is missing. Set isEnd true on the last node.
For search, walk each letter. If a child is missing, return false. At the end, return the isEnd of the final node.
For startsWith, walk each letter of the prefix. If a child is missing, return false. If you reach the end, return true.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version stores children in a plain dictionary, which is Python’s built-in hash map.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> child TrieNode
        self.is_end = False  # True if a word ends here


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

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:        # child missing
                cur.children[ch] = TrieNode() # create it
            cur = cur.children[ch]            # step down
        cur.is_end = True                     # mark word end

    def search(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:        # letter missing
                return False
            cur = cur.children[ch]
        return cur.is_end                     # full word only

    def starts_with(self, prefix):
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:        # path breaks
                return False
            cur = cur.children[ch]
        return True                           # prefix path exists


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

The output of the above code will be:

True
False
True
True

Let us walk the Python version line by line, because it shows the idea with the least noise.

self.children = {} gives each node a dictionary from a letter to the next node. We use a dictionary so a missing letter is just a missing key. self.is_end = False is the flag that marks where a full word stops. Without this flag we could not tell “app” the word from “app” the prefix of “apple”.

In insert, we set cur = self.root and walk each letter. The line if ch not in cur.children checks whether the path already has this letter. If not, cur.children[ch] = TrieNode() builds the new node. Then cur = cur.children[ch] moves us one level down. After the loop, cur.is_end = True marks the final node as a real word end.

In search, we walk the same way. The moment ch not in cur.children is true, the word cannot be there, so we return False. If we survive the loop, return cur.is_end is the answer. We must return the flag, not just True. Reaching the node only means the path exists, not that a word ended there.

In starts_with, the only change is the last line. We return True as long as the path exists. We never look at is_end, because a prefix does not need to be a full word.

⏱️ Time and Space Complexity

The naive list scans every stored word on each lookup, so it depends on how many words you have. The trie depends only on the length of the word you are looking up. Let L be the length of the word. Each operation walks L nodes, so it is O(L). The space grows with the total number of letters stored across all words.

Operation	Time Complexity	Space Complexity
List of words (search/startsWith)	O(n * L)	O(total letters)
Trie insert / search / startsWith	O(L)	O(total letters)

Tip

In an interview, draw the tree for two words that share a prefix, like “app” and “apple”. The picture makes the isEnd flag obvious. That flag is the part people forget, and it is exactly what splits search from startsWith.

🧩 Key Takeaways

✅ A trie stores words as paths of letters, so words with a shared prefix share a path.
✅ Each node has a map of children and an isEnd flag that marks a complete word.
✅ search returns the isEnd of the last node, while startsWith just checks the path exists.
✅ Every operation costs O(L), the length of the word, not the number of words.
✅ Forgetting the isEnd flag is the classic bug, since you then cannot tell a word from a prefix.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Design Add and Search Words Data Structure
Word Search II

Previous Interval List Intersections Next Design Add and Search Words Data Structure

Implement Trie (Prefix Tree)

Follow Us

Follow Us