Advanced · Module 19 · Lesson 1 of 4
Tries
A trie stores strings as paths from a root, one character per edge, so words with a common prefix share nodes. Lookups and prefix queries cost time proportional to the query's length, however many words are stored.
By the end you can
- Build a trie with insert, search and prefix search, and state their costs
- Use a trie to drive searches over many words at once, such as autocomplete and grid word search
- Weigh a trie's memory cost against a hash set or sorted array, and know the compressed variants
Builds on Hash maps in your language, Backtracking basics.
01 · A question first
Typing "pro" into a search box shows suggestions before you type the next letter, drawn from millions of past queries. A hash set can say whether "pro" itself is a word, but not which words start with it. A tree whose paths spell out the words answers in three steps. What does that tree look like?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Strings as paths
- Operations and their cost
- Representing children
- Searching many words at once
- Tries in real systems
- When to reach for a trie
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Asked in interviews
Something wrong with this lesson? Report a problem