What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Trie (Prefix Tree)

The problem

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

A trie ("try") or prefix tree is a tree structure purpose-built for storing and looking up a set of strings efficiently, and it underlies things like autocomplete and spellcheckers.

Implement a Trie class:

Trie() starts with an empty trie.
void insert(String word) adds word to the trie.
boolean search(String word) returns true only if word itself was previously inserted.
boolean startsWith(String prefix) returns true if any inserted word begins with prefix.

Example 1

Input:["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:[null, null, true, false, true, null, true]

After inserting "apple", search("apple") is true, search("app") is false (only a prefix so far), and startsWith("app") is true. After inserting "app", search("app") is true.

Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Invariant: Every inserted word is a path from root whose last node has is_end = True, and every node on any path is a prefix of some inserted word.

Words that share a prefix share one path from root, so any prefix is found by walking one child per letter. insert creates missing children with setdefault and sets is_end on the last node; search and startsWith share _walk. This is correct because a path exists exactly when some inserted word has that prefix, and is_end marks exactly the nodes where a whole word stopped. The trap is skipping is_end in search: after inserting "apple", search("app") would return true.

See it run

Trie: insert, search and startsWith, ops = insert("apple"), insert("apt"), search("app"), startsWith("app"), insert("app"), search("app")

call none yet

Each circle is a node, and the letter inside is the edge that leads to it from its parent. Words that share a prefix share nodes.

here the node the walk is at
new node a node that insert just created
path a node or link the walk already followed
is_end a node where a whole word ends
here+is_end the walk is at a node where a word ends

The trie holds only root. root has no children and is_end is False.

characters read

empty

words stored

empty

1 / 21

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Not this one if…

Only whole keys are ever compared, never prefixes, as in Group Anagrams (LC 49). See Hash Map

Deep Dive

Why shared prefixes share nodes

A trie stores strings as paths. Each node stands for one prefix. Each edge is one character, kept in children. The path from root to a node spells the prefix.

insert follows the word one character at a time. For each character, setdefault returns the child if it exists, and creates it if it does not. So a second word that starts the same way reuses the first word's nodes.

Example: insert("apple") creates 5 nodes, for the prefixes a, ap, app, appl and apple. Then insert("apt") reuses the nodes for a and ap, and creates only one node, for apt. The trie now has 6 character nodes for 8 letters.

After the final insert("app"), the trie still has 6 character nodes, because every prefix of "app" was on the path already. Only is_end changes, on the node for "app".

This is why the card's invariant says that every node on any path is a prefix of some inserted word. A node is created only while some word is being inserted along that path.

What `is_end` adds

The path tells you that some word starts with the string. It does not tell you that the string is itself a word. is_end carries that second fact.

In the example, the trie holds "apple" and "apt", and then search("app") runs. _walk reaches the node for "app", because both words pass through it. The node exists, but is_end is False there. So search returns False. startsWith("app") returns True for the same node, because it needs only the node.

After insert("app"), the node for "app" has is_end = True, and search("app") returns True.

The two methods differ by one condition. search returns node is not None and node.is_end. startsWith returns node is not None. Writing the first without and node.is_end is the card's main trap.

The cost depends on the word, not the dictionary

Each of insert, search and startsWith visits one node per character. That is O(L) time, where L is the length of the word or prefix. The number of stored words does not appear in the cost.

Compare this with a set of words. A set finds a whole word in O(L) on average, because it hashes the string. But it cannot answer startsWith. That question needs a scan over every stored word.

The space is O(total characters) in the worst case, which is when no two words share a prefix. Shared prefixes lower it. In the example, 5 + 3 + 3 = 11 letters were inserted, and the trie holds 6 character nodes.

The card stores children in a dictionary. Each node then keeps only the characters it needs. An array of 26 slots per node is faster to index, but it uses 26 slots even for a node with one child.

Where to use the same walk

The same children and is_end fields serve many problems. Design Add and Search Words Data Structure (LC 211) lets . match any letter, so the search tries every child at that character. Word Search II (LC 212) walks a trie of all target words while a DFS moves on the board, and it stops a path when the trie has no matching child.

Replace Words (LC 648) walks each word and stops at the first node with is_end = True. Search Suggestions System (LC 1268) walks to the node for the typed prefix, and then collects words below that node.

In each case, the move is the same: a missing child means that no stored word has this prefix, so the search can stop early.

60-Second Pitch

"I store the dictionary as a tree of characters. Each edge is a letter, and each node is a prefix of some word. insert walks the word and creates missing children with setdefault, then sets is_end on the last node. Words that share a prefix share nodes. _walk follows one child per character and returns None when a child is missing. startsWith needs only that node, and search also needs is_end. Each operation costs O(L) for a word of length L. The space is O(total characters) in the worst case."

Common Questions

What is the time and space complexity of the trie?: Each operation is O(L) time, where L is the length of the string. The space is O(total characters) in the worst case, which is when no two words share a prefix. The number of words does not change the time of one operation.
Why use a trie when a hash set stores words?: A set answers whole-word lookups well, but startsWith needs a scan over every word. The trie answers a prefix question by walking one path of L nodes. The trie is also the base for autocomplete and for board searches that stop early.
What are the options for children, and how do they compare?: A dictionary stores only the characters that exist, so a sparse node is small. An array of 26 slots indexes faster, but each node holds 26 slots, even with one child. The dictionary is a safe default, and it also works for non-lowercase alphabets.
How would you list all words that start with a prefix?: Use _walk(prefix) to reach the node. If it is None, return an empty list. Otherwise run a DFS from that node, and collect the path whenever is_end is True. The cost is O(L) for the walk plus the size of the subtree below the node.
How would you delete a word?: Walk to the last node and set is_end = False. This is enough for correct answers. To free memory, also remove the nodes on the path that have no children and no is_end, going from the bottom up. Stop at the first node that another word still needs.

SWE Reasoning

Spot it

Many words or prefixes are checked against one dictionary.
The question is about a prefix: autocomplete, "does any word start with this", word search on a board.
A set of words answers whole-word lookups, but you also need prefix lookups.
Characters arrive one at a time, and you want to stop as soon as no word can match.
A wildcard such as . replaces one letter.

The invariant, step by step

Trie() creates root with empty children and is_end = False.
insert(word) starts at root. For each ch, children.setdefault(ch, TrieNode()) returns the existing child or creates a new one. Then node moves to that child.
After the last character, node.is_end = True. The path from root now spells word, and its last node marks a whole word.
_walk(s) starts at root and follows children[ch] for each character. If ch is not in node.children, it returns None.
A path for s exists exactly when some inserted word starts with s, because nodes are created only while inserting.
search(word) also requires node.is_end, which is set only where a whole word stopped. startsWith(prefix) needs only the path.

Traps

Skipping is_end in search. After insert("apple"), search("app") returns True, though "app" was never inserted.
Creating nodes in _walk. With setdefault in _walk, a read adds nodes. After search("cat") on an empty trie, startsWith("ca") returns True.
Not marking the end. If insert never sets is_end, search returns False for every word.
Setting is_end before the loop. node.is_end = True placed before the for loop marks root. Then search("") returns True, and no real word is marked.
Sharing one TrieNode between children. A table built as [TrieNode()] * 26 puts one node object in all 26 slots, so every letter leads to the same node. Create a new TrieNode() for each child.
Empty string. _walk("") returns root, so startsWith("") is True and search("") is False unless the empty word was inserted. LeetCode limits words to length 1 or more.

Practice

Canonical LeetCode:Implement Trie (Prefix Tree) (LC 208)Design Add and Search Words Data Structure (LC 211)Word Search II (LC 212)Stream of Characters (LC 1032)Implement Trie II (Prefix Tree) (LC 1804)Design Search Autocomplete System (LC 642)Longest Word in Dictionary (LC 720)Longest Common Prefix (LC 14)

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Trie (Prefix Tree)

The problem

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

A trie ("try") or prefix tree is a tree structure purpose-built for storing and looking up a set of strings efficiently, and it underlies things like autocomplete and spellcheckers.

Implement a Trie class:

Trie() starts with an empty trie.
void insert(String word) adds word to the trie.
boolean search(String word) returns true only if word itself was previously inserted.
boolean startsWith(String prefix) returns true if any inserted word begins with prefix.

Example 1

Input:["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:[null, null, true, false, true, null, true]

After inserting "apple", search("apple") is true, search("app") is false (only a prefix so far), and startsWith("app") is true. After inserting "app", search("app") is true.

Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Invariant: Every inserted word is a path from root whose last node has is_end = True, and every node on any path is a prefix of some inserted word.

See it run

Trie: insert, search and startsWith, ops = insert("apple"), insert("apt"), search("app"), startsWith("app"), insert("app"), search("app")

call none yet

Each circle is a node, and the letter inside is the edge that leads to it from its parent. Words that share a prefix share nodes.

here the node the walk is at
new node a node that insert just created
path a node or link the walk already followed
is_end a node where a whole word ends
here+is_end the walk is at a node where a word ends

The trie holds only root. root has no children and is_end is False.

characters read

empty

words stored

empty

1 / 21

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Not this one if…

Only whole keys are ever compared, never prefixes, as in Group Anagrams (LC 49). See Hash Map

Deep Dive

Why shared prefixes share nodes

A trie stores strings as paths. Each node stands for one prefix. Each edge is one character, kept in children. The path from root to a node spells the prefix.

After the final insert("app"), the trie still has 6 character nodes, because every prefix of "app" was on the path already. Only is_end changes, on the node for "app".

This is why the card's invariant says that every node on any path is a prefix of some inserted word. A node is created only while some word is being inserted along that path.

What `is_end` adds

The path tells you that some word starts with the string. It does not tell you that the string is itself a word. is_end carries that second fact.

After insert("app"), the node for "app" has is_end = True, and search("app") returns True.

The cost depends on the word, not the dictionary

Each of insert, search and startsWith visits one node per character. That is O(L) time, where L is the length of the word or prefix. The number of stored words does not appear in the cost.

Compare this with a set of words. A set finds a whole word in O(L) on average, because it hashes the string. But it cannot answer startsWith. That question needs a scan over every stored word.

The card stores children in a dictionary. Each node then keeps only the characters it needs. An array of 26 slots per node is faster to index, but it uses 26 slots even for a node with one child.

Where to use the same walk

In each case, the move is the same: a missing child means that no stored word has this prefix, so the search can stop early.

60-Second Pitch

Common Questions

What is the time and space complexity of the trie?: Each operation is O(L) time, where L is the length of the string. The space is O(total characters) in the worst case, which is when no two words share a prefix. The number of words does not change the time of one operation.
Why use a trie when a hash set stores words?: A set answers whole-word lookups well, but startsWith needs a scan over every word. The trie answers a prefix question by walking one path of L nodes. The trie is also the base for autocomplete and for board searches that stop early.
What are the options for children, and how do they compare?: A dictionary stores only the characters that exist, so a sparse node is small. An array of 26 slots indexes faster, but each node holds 26 slots, even with one child. The dictionary is a safe default, and it also works for non-lowercase alphabets.
How would you list all words that start with a prefix?: Use _walk(prefix) to reach the node. If it is None, return an empty list. Otherwise run a DFS from that node, and collect the path whenever is_end is True. The cost is O(L) for the walk plus the size of the subtree below the node.
How would you delete a word?: Walk to the last node and set is_end = False. This is enough for correct answers. To free memory, also remove the nodes on the path that have no children and no is_end, going from the bottom up. Stop at the first node that another word still needs.

SWE Reasoning

Spot it

Many words or prefixes are checked against one dictionary.
The question is about a prefix: autocomplete, "does any word start with this", word search on a board.
A set of words answers whole-word lookups, but you also need prefix lookups.
Characters arrive one at a time, and you want to stop as soon as no word can match.
A wildcard such as . replaces one letter.

The invariant, step by step

Trie() creates root with empty children and is_end = False.
insert(word) starts at root. For each ch, children.setdefault(ch, TrieNode()) returns the existing child or creates a new one. Then node moves to that child.
After the last character, node.is_end = True. The path from root now spells word, and its last node marks a whole word.
_walk(s) starts at root and follows children[ch] for each character. If ch is not in node.children, it returns None.
A path for s exists exactly when some inserted word starts with s, because nodes are created only while inserting.
search(word) also requires node.is_end, which is set only where a whole word stopped. startsWith(prefix) needs only the path.

Traps

Skipping is_end in search. After insert("apple"), search("app") returns True, though "app" was never inserted.
Creating nodes in _walk. With setdefault in _walk, a read adds nodes. After search("cat") on an empty trie, startsWith("ca") returns True.
Not marking the end. If insert never sets is_end, search returns False for every word.
Setting is_end before the loop. node.is_end = True placed before the for loop marks root. Then search("") returns True, and no real word is marked.
Sharing one TrieNode between children. A table built as [TrieNode()] * 26 puts one node object in all 26 slots, so every letter leads to the same node. Create a new TrieNode() for each child.
Empty string. _walk("") returns root, so startsWith("") is True and search("") is False unless the empty word was inserted. LeetCode limits words to length 1 or more.

Practice

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Trie (Prefix Tree)

The problem

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

A trie ("try") or prefix tree is a tree structure purpose-built for storing and looking up a set of strings efficiently, and it underlies things like autocomplete and spellcheckers.

Implement a Trie class:

Trie() starts with an empty trie.
void insert(String word) adds word to the trie.
boolean search(String word) returns true only if word itself was previously inserted.
boolean startsWith(String prefix) returns true if any inserted word begins with prefix.

Example 1

Input:["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:[null, null, true, false, true, null, true]

After inserting "apple", search("apple") is true, search("app") is false (only a prefix so far), and startsWith("app") is true. After inserting "app", search("app") is true.

Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Invariant: Every inserted word is a path from root whose last node has is_end = True, and every node on any path is a prefix of some inserted word.

See it run

Trie: insert, search and startsWith, ops = insert("apple"), insert("apt"), search("app"), startsWith("app"), insert("app"), search("app")

call none yet

Each circle is a node, and the letter inside is the edge that leads to it from its parent. Words that share a prefix share nodes.

here the node the walk is at
new node a node that insert just created
path a node or link the walk already followed
is_end a node where a whole word ends
here+is_end the walk is at a node where a word ends

The trie holds only root. root has no children and is_end is False.

characters read

empty

words stored

empty

1 / 21

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Not this one if…

Only whole keys are ever compared, never prefixes, as in Group Anagrams (LC 49). See Hash Map

Deep Dive

Why shared prefixes share nodes

A trie stores strings as paths. Each node stands for one prefix. Each edge is one character, kept in children. The path from root to a node spells the prefix.

After the final insert("app"), the trie still has 6 character nodes, because every prefix of "app" was on the path already. Only is_end changes, on the node for "app".

This is why the card's invariant says that every node on any path is a prefix of some inserted word. A node is created only while some word is being inserted along that path.

What `is_end` adds

The path tells you that some word starts with the string. It does not tell you that the string is itself a word. is_end carries that second fact.

After insert("app"), the node for "app" has is_end = True, and search("app") returns True.

The cost depends on the word, not the dictionary

Each of insert, search and startsWith visits one node per character. That is O(L) time, where L is the length of the word or prefix. The number of stored words does not appear in the cost.

Compare this with a set of words. A set finds a whole word in O(L) on average, because it hashes the string. But it cannot answer startsWith. That question needs a scan over every stored word.

The card stores children in a dictionary. Each node then keeps only the characters it needs. An array of 26 slots per node is faster to index, but it uses 26 slots even for a node with one child.

Where to use the same walk

In each case, the move is the same: a missing child means that no stored word has this prefix, so the search can stop early.

60-Second Pitch

Common Questions

What is the time and space complexity of the trie?: Each operation is O(L) time, where L is the length of the string. The space is O(total characters) in the worst case, which is when no two words share a prefix. The number of words does not change the time of one operation.
Why use a trie when a hash set stores words?: A set answers whole-word lookups well, but startsWith needs a scan over every word. The trie answers a prefix question by walking one path of L nodes. The trie is also the base for autocomplete and for board searches that stop early.
What are the options for children, and how do they compare?: A dictionary stores only the characters that exist, so a sparse node is small. An array of 26 slots indexes faster, but each node holds 26 slots, even with one child. The dictionary is a safe default, and it also works for non-lowercase alphabets.
How would you list all words that start with a prefix?: Use _walk(prefix) to reach the node. If it is None, return an empty list. Otherwise run a DFS from that node, and collect the path whenever is_end is True. The cost is O(L) for the walk plus the size of the subtree below the node.
How would you delete a word?: Walk to the last node and set is_end = False. This is enough for correct answers. To free memory, also remove the nodes on the path that have no children and no is_end, going from the bottom up. Stop at the first node that another word still needs.

SWE Reasoning

Spot it

Many words or prefixes are checked against one dictionary.
The question is about a prefix: autocomplete, "does any word start with this", word search on a board.
A set of words answers whole-word lookups, but you also need prefix lookups.
Characters arrive one at a time, and you want to stop as soon as no word can match.
A wildcard such as . replaces one letter.

The invariant, step by step

Trie() creates root with empty children and is_end = False.
insert(word) starts at root. For each ch, children.setdefault(ch, TrieNode()) returns the existing child or creates a new one. Then node moves to that child.
After the last character, node.is_end = True. The path from root now spells word, and its last node marks a whole word.
_walk(s) starts at root and follows children[ch] for each character. If ch is not in node.children, it returns None.
A path for s exists exactly when some inserted word starts with s, because nodes are created only while inserting.
search(word) also requires node.is_end, which is set only where a whole word stopped. startsWith(prefix) needs only the path.

Traps

Skipping is_end in search. After insert("apple"), search("app") returns True, though "app" was never inserted.
Creating nodes in _walk. With setdefault in _walk, a read adds nodes. After search("cat") on an empty trie, startsWith("ca") returns True.
Not marking the end. If insert never sets is_end, search returns False for every word.
Setting is_end before the loop. node.is_end = True placed before the for loop marks root. Then search("") returns True, and no real word is marked.
Sharing one TrieNode between children. A table built as [TrieNode()] * 26 puts one node object in all 26 slots, so every letter leads to the same node. Create a new TrieNode() for each child.
Empty string. _walk("") returns root, so startsWith("") is True and search("") is False unless the empty word was inserted. LeetCode limits words to length 1 or more.

Practice

Theory Context•Advanced Data Structures

Builds on Hash Map, which you haven’t finished yet.

P1MediumMental model~7 min speedrun

Trie (Prefix Tree)

The problem

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

A trie ("try") or prefix tree is a tree structure purpose-built for storing and looking up a set of strings efficiently, and it underlies things like autocomplete and spellcheckers.

Implement a Trie class:

Trie() starts with an empty trie.
void insert(String word) adds word to the trie.
boolean search(String word) returns true only if word itself was previously inserted.
boolean startsWith(String prefix) returns true if any inserted word begins with prefix.

Example 1

Input:["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

Output:[null, null, true, false, true, null, true]

After inserting "apple", search("apple") is true, search("app") is false (only a prefix so far), and startsWith("app") is true. After inserting "app", search("app") is true.

Trie

strings / dictionary ➔ 26-ary tree of characters ➔ O(L) prefix search

Spot it when: You check many words or prefixes against one dictionary: autocomplete, word search on a board, wildcard lookups, a stream of characters.

Trie

Python

1	from typing import Optional
2
3	class TrieNode:
4	def __init__(self) -> None:
5	self.children: dict[str, "TrieNode"] = {} # One edge per next character
6	self.is_end = False # A whole word ends here
7
8	class Trie:
9	"""Implement Trie (Prefix Tree) with a shared _walk traversal helper.
10	Time: O(L) per operation, L = word length \| Space: O(total characters)
11	"""
12	def __init__(self) -> None:
13	self.root = TrieNode()
14
15	def _walk(self, s: str) -> Optional[TrieNode]:
16	node = self.root
17
18	# 1. Follow One Edge Per Character:
19	# Moving to the matching child reconstructs the path s spells out one letter at a time.
20	# If a child is missing, no inserted word ever created this prefix, so the walk stops early.
21	for ch in s:
22	if ch not in node.children:
23	return None # Path breaks: no word has this prefix
24	node = node.children[ch]
25	return node
26
27	def insert(self, word: str) -> None:
28	node = self.root
29
30	# 1. Create Or Reuse One Edge Per Character:
31	# setdefault reuses the child already built by an earlier word that shares this prefix,
32	# and creates a new child only the first time a path through this character is needed.
33	for ch in word:
34	node = node.children.setdefault(ch, TrieNode()) # Create missing edges
35	node.is_end = True # Mark the end, or search() can't tell "app" from "apple"
36
37	def search(self, word: str) -> bool:
38	node = self._walk(word)
39	return node is not None and node.is_end # Path exists AND a word ends here
40
41	def startsWith(self, prefix: str) -> bool:
42	return self._walk(prefix) is not None # Any path is enough for a prefix

Invariant: Every inserted word is a path from root whose last node has is_end = True, and every node on any path is a prefix of some inserted word.

See it run

Trie: insert, search and startsWith, ops = insert("apple"), insert("apt"), search("app"), startsWith("app"), insert("app"), search("app")

call none yet

Each circle is a node, and the letter inside is the edge that leads to it from its parent. Words that share a prefix share nodes.

here the node the walk is at
new node a node that insert just created
path a node or link the walk already followed
is_end a node where a whole word ends
here+is_end the walk is at a node where a word ends

The trie holds only root. root has no children and is_end is False.

characters read

empty

words stored

empty

1 / 21

Gotchas1 of 5

The trap
Gotcha 1: Returning node is not None in search
Mistake
```
return node is not None
```
Fix
```
return node is not None and node.is_end
```
What happens: Reaching a node only proves that some inserted word starts with word. After insert("apple"), the path for "app" exists. Only node.is_end says that a whole word stopped at that node.
Example: insert("apple"), then search("app")
Mistake: returns TrueFix: returns False
Gotcha 2: Creating nodes in _walk with setdefault
Mistake
```
node = node.children.setdefault(ch, TrieNode())
```
Fix
```
if ch not in node.children:
    return None
node = node.children[ch]
```
What happens: _walk serves search and startsWith, which only read the trie. With setdefault, every lookup adds the missing nodes. After search("cat"), the path "c", "a", "t" exists, so startsWith("ca") returns True. No word that starts with "ca" was ever inserted.
Example: search("cat") on an empty trie, then startsWith("ca")
Mistake: returns TrueFix: returns False
Gotcha 3: Checking is_end in startsWith
Mistake
```
node = self._walk(prefix)
return node is not None and node.is_end
```
Fix
```
return self._walk(prefix) is not None
```
What happens: A prefix only needs a path. After insert("apple"), startsWith("app") must be True. The node for "app" has is_end False, so the extra check returns False.
Example: insert("apple"), then startsWith("app")
Mistake: returns FalseFix: returns True
Gotcha 4: Following only one child at a . in wildcard search
What happens: In Design Add and Search Words Data Structure (LC 211), a . matches any one letter. So at a ., the search must try every child of the current node. The loop in _walk can follow only one child. Write the search recursively, and return True as soon as one branch matches.
Gotcha 5: Reporting a word every time the search reaches it
What happens: In Word Search II (LC 212), the grid can spell the same word along two different paths. Store the full word at its end node. Add it to the answer, then clear it at that node. The second path then finds nothing to report.

Not this one if…

Only whole keys are ever compared, never prefixes, as in Group Anagrams (LC 49). See Hash Map

Deep Dive

Why shared prefixes share nodes

A trie stores strings as paths. Each node stands for one prefix. Each edge is one character, kept in children. The path from root to a node spells the prefix.

After the final insert("app"), the trie still has 6 character nodes, because every prefix of "app" was on the path already. Only is_end changes, on the node for "app".

This is why the card's invariant says that every node on any path is a prefix of some inserted word. A node is created only while some word is being inserted along that path.

What `is_end` adds

The path tells you that some word starts with the string. It does not tell you that the string is itself a word. is_end carries that second fact.

After insert("app"), the node for "app" has is_end = True, and search("app") returns True.

The cost depends on the word, not the dictionary

Each of insert, search and startsWith visits one node per character. That is O(L) time, where L is the length of the word or prefix. The number of stored words does not appear in the cost.

Compare this with a set of words. A set finds a whole word in O(L) on average, because it hashes the string. But it cannot answer startsWith. That question needs a scan over every stored word.

The card stores children in a dictionary. Each node then keeps only the characters it needs. An array of 26 slots per node is faster to index, but it uses 26 slots even for a node with one child.

Where to use the same walk

In each case, the move is the same: a missing child means that no stored word has this prefix, so the search can stop early.

60-Second Pitch

Common Questions

What is the time and space complexity of the trie?: Each operation is O(L) time, where L is the length of the string. The space is O(total characters) in the worst case, which is when no two words share a prefix. The number of words does not change the time of one operation.
Why use a trie when a hash set stores words?: A set answers whole-word lookups well, but startsWith needs a scan over every word. The trie answers a prefix question by walking one path of L nodes. The trie is also the base for autocomplete and for board searches that stop early.
What are the options for children, and how do they compare?: A dictionary stores only the characters that exist, so a sparse node is small. An array of 26 slots indexes faster, but each node holds 26 slots, even with one child. The dictionary is a safe default, and it also works for non-lowercase alphabets.
How would you list all words that start with a prefix?: Use _walk(prefix) to reach the node. If it is None, return an empty list. Otherwise run a DFS from that node, and collect the path whenever is_end is True. The cost is O(L) for the walk plus the size of the subtree below the node.
How would you delete a word?: Walk to the last node and set is_end = False. This is enough for correct answers. To free memory, also remove the nodes on the path that have no children and no is_end, going from the bottom up. Stop at the first node that another word still needs.

SWE Reasoning

Spot it

Many words or prefixes are checked against one dictionary.
The question is about a prefix: autocomplete, "does any word start with this", word search on a board.
A set of words answers whole-word lookups, but you also need prefix lookups.
Characters arrive one at a time, and you want to stop as soon as no word can match.
A wildcard such as . replaces one letter.

The invariant, step by step

Trie() creates root with empty children and is_end = False.
insert(word) starts at root. For each ch, children.setdefault(ch, TrieNode()) returns the existing child or creates a new one. Then node moves to that child.
After the last character, node.is_end = True. The path from root now spells word, and its last node marks a whole word.
_walk(s) starts at root and follows children[ch] for each character. If ch is not in node.children, it returns None.
A path for s exists exactly when some inserted word starts with s, because nodes are created only while inserting.
search(word) also requires node.is_end, which is set only where a whole word stopped. startsWith(prefix) needs only the path.

Traps

Skipping is_end in search. After insert("apple"), search("app") returns True, though "app" was never inserted.
Creating nodes in _walk. With setdefault in _walk, a read adds nodes. After search("cat") on an empty trie, startsWith("ca") returns True.
Not marking the end. If insert never sets is_end, search returns False for every word.
Setting is_end before the loop. node.is_end = True placed before the for loop marks root. Then search("") returns True, and no real word is marked.
Sharing one TrieNode between children. A table built as [TrieNode()] * 26 puts one node object in all 26 slots, so every letter leads to the same node. Create a new TrieNode() for each child.
Empty string. _walk("") returns root, so startsWith("") is True and search("") is False unless the empty word was inserted. LeetCode limits words to length 1 or more.

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

Trie

See it run

Deep Dive

Why shared prefixes share nodes

What is_end adds

The cost depends on the word, not the dictionary

Where to use the same walk

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

Trie

See it run

Deep Dive

Why shared prefixes share nodes

What is_end adds

The cost depends on the word, not the dictionary

Where to use the same walk

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

Trie

See it run

Deep Dive

Why shared prefixes share nodes

What is_end adds

The cost depends on the word, not the dictionary

Where to use the same walk

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

Implement Trie (Prefix Tree) (LC 208)(opens leetcode.com)

Trie

See it run

Deep Dive

Why shared prefixes share nodes

What is_end adds

The cost depends on the word, not the dictionary

Where to use the same walk

60-Second Pitch

Common Questions

SWE Reasoning

Spot it

The invariant, step by step

Traps

Practice

What `is_end` adds

What `is_end` adds

What `is_end` adds

What `is_end` adds