Implement Trie (Prefix Tree)
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Build a Trie with insert(word), search(word) and startsWith(prefix).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does each node need to remember about its children?
- Hint 2How do you tell the stored word "app" apart from the prefix of "apple"?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A phone book with tabs: first the tab for "a", inside it the tab "p", inside that another "p". Words that start with "app" all share these three tabs. To check if "app" is a stored word you follow the tabs and look for a red sticker ("a word ends here"). To check if anything starts with "app" you only need the tabs to exist.
- The obvious way
Keep a list of words and scan it: O(words x length) per query.
- The key insight
Each node has a dictionary letter -> child node and a flag is_word. insert walks the letters creating missing nodes and sets the flag at the end. A helper walk(text) returns the node reached after following the letters (or nothing). search = the node exists and is_word; startsWith = the node exists.
- The algorithm
- Node: children dictionary + is_word flag.
- insert: follow or create each letter's child, flag the last node.
- search: follow letters; True only if the end node is flagged.
- startsWith: True if the letters can be followed at all.
Watch it run
Exampleinsert apple; search apple; search app; startsWith app; insert app; search app
insert "apple": create the path a, p, p, l, e and flag the last node.
path a-p-p-l-e*
Where people slip
- search needs the end flag; startsWith does not.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
class Trie:
def __init__(self):
self.children = {} # letter -> the next tab
self.is_word = False # red sticker: a word ends here
def insert(self, word):
node = self
for letter in word:
if letter not in node.children:
node.children[letter] = Trie()
node = node.children[letter]
node.is_word = True
def _walk(self, text):
node = self
for letter in text:
node = node.children.get(letter)
if node is None:
return None
return node
def search(self, word):
node = self._walk(word)
return node is not None and node.is_word
def startsWith(self, prefix):
return self._walk(prefix) is not NoneNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.