Math for coding interviews/Strings as paths through a tree
Tries: Strings as Paths Through a Tree
In a trie, each letter of a word is one step down the tree. The word "cat" is stored as: root → c → a → t. The depth of the tree equals the length of the longest word, not the number of words. This is what makes prefix search so fast.
See it for yourself
A tree where each edge is labeled with a letter. Trace the path for "cat": follow the c edge, then a, then t. The node at the end is marked as a complete word.
Strings as paths through a tree
In a trie, each letter of a word is one step down the tree. The word "cat" is stored as: root → c → a → t. The depth of the tree equals the length of the longest word, not the number of words. This is what makes prefix search so fast.
Think of it this way: A filing system where files are sorted one letter at a time. All files starting with "c" are in one drawer, within that drawer all "ca" files are in one folder. Finding any file means navigating letter by letter.
For algorithms: Searching for a word of length L takes exactly L steps, regardless of how many words are in the trie. That is O(L) - not O(n) where n is the number of words.
Real-world analogy
A filing system where files are sorted one letter at a time. All files starting with "c" are in one drawer, within that drawer all "ca" files are in one folder. Finding any file means navigating letter by letter.
Why it matters in interviews
Searching for a word of length L takes exactly L steps, regardless of how many words are in the trie. That is O(L) - not O(n) where n is the number of words.