Back
+20 XP
Concept

Trie (Prefix Tree) for Lightning Fast Search

A Trie is a tree where each node represents a character. Looking up prefixes or autocompleting words takes $O(L)$ time, where $L$ is word length, regardless of having 10 or 10,000,000 words in the dictionary 🌲.

python
class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        curr = self.root
        for char in word:
            curr = curr.setdefault(char, {})
        curr["$"] = True  # Marks end of complete word 🏁

    def starts_with(self, prefix):
        curr = self.root
        for char in prefix:
            if char not in curr: return False
            curr = curr[char]
        return True

t = Trie()
t.insert("python")
print(t.starts_with("py"))   # True 🌲
print(t.starts_with("java")) # False ❌

# 12. Trie (Prefix Tree) for Lightning Fast Search A Trie is a tree where each node represents a character. Looking up prefixes or autocompleting words takes $O(L)$ time, where $L$ is word length, regardless of having 10 or 10,000,000 words in the dictionary 🌲. ```python class Trie: def __init__(self): self.root = {} def insert(self, word): curr = self.root for char in word: curr = curr.setdefault(char, {}) curr["$"] = True # Marks end of complete word 🏁 def starts_with(self, prefix): curr = self.root for char in prefix: if char not in curr: return False curr = curr[char] return True t = Trie() t.insert("python") print(t.starts_with("py")) # True 🌲 print(t.starts_with("java")) # False ❌ ``` Search engines and phone keyboards use Tries to suggest instant auto-completions as your fingers type each letter! 🌲 --- ### Question What is the time complexity of checking if a prefix exists in a Trie containing $N$ words of maximum length $L$? 🧠 - [ ] a. $O(L)$ dependent strictly on the length of the prefix string, independent of dictionary size $N$ 🌲 - [ ] b. $O(N)$ linear search through all words - [ ] c. $O(N \log N)$ - [ ] d. $O(1)$ constant time --- ### Challenge Build a minimal Trie. Insert `"api"`. Write `has_prefix(prefix)` returning True if prefix path exists in root dict. Print `has_prefix("ap")` and `has_prefix("zo")`. 🎯 <details> <summary>Solution</summary> ```python root = {} def insert(word): curr = root for ch in word: curr = curr.setdefault(ch, {}) curr["$"] = True def has_prefix(prefix): curr = root for ch in prefix: if ch not in curr: return False curr = curr[ch] return True insert("api") print(has_prefix("ap")) print(has_prefix("zo")) ``` </details>

Checkpoint

What is the time complexity of checking if a prefix exists in a Trie containing $N$ words of maximum length $L$? 🧠

Practice

Build a minimal Trie. Insert `"api"`. Write `has_prefix(prefix)` returning True if prefix path exists in root dict. Print `has_prefix("ap")` and `has_prefix("zo")`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks