Implement Trie (Prefix Tree)

Design a data structure that supports insert, search, and startsWith.

10 min read

Time: O(n)

Space: O(1)

Solve on LeetCode

Problem Description

Implement Trie class:

insert(word): Inserts string word.
search(word): Returns true if string word is in the trie.
startsWith(prefix): Returns true if there is a previously inserted string having prefix.

Interactive Visualization

Step 1 / 1

Visualization coming soon...

Initializing...

Custom Input

Watch how insert creates new nodes only when necessary, and search traverses existing paths.

Algorithm Strategy

Node Structure: Each node contains a map/array of size 26 (for 'a'-'z') and a boolean isEnd.
Insert: Traverse down; create nodes if missing. Mark last node as isEnd.
Search: Traverse down; if node missing -> return false. At end, return node.isEnd.
StartsWith: Traverse down; if node missing -> return false. If loop finishes, return true.

Dry Run: Insert 'cat'

Char	Node Exists?	Action
'c'	No	Create 'c' node. Move to 'c'.
'a'	No	Create 'a' node. Move to 'a'.
't'	No	Create 't' node. Move to 't'.
End	-	Mark 't' node as `isEnd=True`.

Solution

O(L) Time per operation where L is word length.

1class TrieNode:
2    def __init__(self):
3        self.children = {}
4        self.is_end = False
5
6class Trie:
7    def __init__(self):
8        self.root = TrieNode()
9
10    def insert(self, word: str) -> None:
11        node = self.root
12        for char in word:
13            if char not in node.children:
14                node.children[char] = TrieNode()
15            node = node.children[char]
16        node.is_end = True
17
18    def search(self, word: str) -> bool:
19        node = self.root
20        for char in word:
21            if char not in node.children:
22                return False
23            node = node.children[char]
24        return node.is_end
25
26    def startsWith(self, prefix: str) -> bool:
27        node = self.root
28        for char in prefix:
29            if char not in node.children:
30                return False
31            node = node.children[char]
32        return True

Edge Cases & Common Mistakes

Check for:

Word is Prefix: Searching for 'app' when 'apple' exists. Should return False (unless 'app' was inserted independently).
Prefix Search: startsWith('app') should return True if 'apple' exists.
Duplication: Inserting 'app' twice shouldn't break anything.

Complexity Analysis

Time Complexity: O(L) for Insert/Search/StartsWith.
Space Complexity: O(N * L) total characters stored.

Previous Problem

Gas Station

Next Problem

Search Suggestions System