Lesson 1 � Intermediate

Trie: Prefix Tree aur Autocomplete

Trie ek special tree data structure hai jo strings ko efficiently store aur search karta hai. Google ka autocomplete, phone directory, spell checker � sab trie pe based hain. Ye O(L) mein search deta hai jahan L = string length.

? 30 min✓ Intermediate✓ Trees basics

Trie hota kya hai?

WHAT

Trie (pronounced "try") ek tree-like data structure hai jismein har node ek character represent karti hai. Root se leaf tak ka path ek complete word banata hai. Common prefixes share hote hain � jaise "cat", "car", "card" mein "ca" common hai.

WHEN

Jab multiple strings ko store karna ho aur prefix-based search chahiye � autocomplete, dictionary, spell checker. Normal string array mein search O(n*L) leta hai, trie mein O(L).

WHERE

Google Search autocomplete, phone directory, word games (Scrabble), IP routing (longest prefix match), T9 predictive text � ye sab trie use karte hain.

Visual: Trie kaise dikhta hai

Words: "cat", "car", "card", "dog"

 (root)
 / \
 c d
 | |
 a o
 / \ |
 t* r* g*
 |
 d*

* = end of word marker

"cat" ✓ c ✓ a ✓ t* (word complete)
"car" ✓ c ✓ a ✓ r* (word complete)
"card" ✓ c ✓ a ✓ r ✓ d* (word complete)
"dog" ✓ d ✓ o ✓ g* (word complete)

Common prefix "ca" is shared!

Key Advantage: Agar tumhe 10,000 words store karne hain jo "pro" se start hain, toh trie mein "p", "r", "o" sirf ek baar store honge. Har word ke liye alag se nahi. Isliye trie space-efficient hai common prefixes ke liye!

Basic Operations: Insert, Search, Delete

class TrieNode:
 def __init__(self):
 self.children = {} # character -> TrieNode
 self.is_end = False # kya ye word ka end hai?

class Trie:
 def __init__(self):
 self.root = TrieNode()
 
 def insert(self, word):
 node = self.root
 for ch in word:
 if ch not in node.children:
 node.children[ch] = TrieNode()
 node = node.children[ch]
 node.is_end = True
 
 def search(self, word):
 node = self.root
 for ch in word:
 if ch not in node.children:
 return False
 node = node.children[ch]
 return node.is_end
 
 def starts_with(self, prefix):
 node = self.root
 for ch in prefix:
 if ch not in node.children:
 return False
 node = node.children[ch]
 return True

# Usage
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("card")
trie.insert("dog")

print(trie.search("car")) # True
print(trie.search("ca")) # False (prefix hai, word nahi)
print(trie.starts_with("ca")) # True
print(trie.search("bat")) # False

Autocomplete Feature

def autocomplete(trie, prefix):
 node = trie.root
 # Prefix tak jao
 for ch in prefix:
 if ch not in node.children:
 return []
 node = node.children[ch]
 
 # Ab us node se saare words collect karo
 results = []
 def dfs(node, current_word):
 if node.is_end:
 results.append(current_word)
 for ch, child_node in node.children.items():
 dfs(child_node, current_word + ch)
 
 dfs(node, prefix)
 return results

# Usage
trie = Trie()
for word in ["pro", "progress", "problem", "produce", "product", "prompt"]:
 trie.insert(word)

print(autocomplete(trie, "pro"))
# ['pro', 'progress', 'problem', 'produce', 'product', 'prompt']

print(autocomplete(trie, "prod"))
# ['produce', 'product']

Trie se Delete karna

def delete(self, word):
 def _delete(node, word, depth):
 if depth == len(word):
 if not node.is_end:
 return False # Word exist nahi karta
 node.is_end = False
 # Agar is node ke koi children nahi toh delete karo
 return len(node.children) == 0
 
 ch = word[depth]
 if ch not in node.children:
 return False
 
 should_delete = _delete(node.children[ch], word, depth + 1)
 
 if should_delete:
 del node.children[ch]
 # Agar current node bhi end nahi hai aur koi children nahi
 return not node.is_end and len(node.children) == 0
 
 return False
 
 _delete(self.root, word, 0)

Memory Optimization: Basic trie mein har node ek dictionary rakhti hai. Production mein compressed trie (radix tree) use hota hai jismein single-child nodes merge ho jaati hain. Space bahut bachti hai.

Try it: code khud likho

Exercise

Question: Trie mein "apple", "app", "banana" insert karo. "app" search karo � True ya False✓ Answer mein True/False daalo.

Question: Trie mein "cat", "car", "card", "dog" hain. "ca" se kitne words start hote hain✓ Answer mein number daalo.

Common mistakes

is_end mark karna bhoolna: Insert karte waqt node.is_end = True
Case sensitivity: Trie case-sensitive hota hai � "Apple" aur "apple" alag hain. Agar case-insensitive chahiye toh insert/search se pehle .lower() karo.
Delete mein children check: Delete karte waqt check karo ki node ke aur koi children hain ya nahi. Agar hain toh sirf is_end = False karo, node mat delete karo � baaki words ka raasta hai.
Space complexity: Trie O(ALPHABET_SIZE * L * N) space le sakta hai jahan N = words, L = avg length. Har word ke liye alag path hota hai agar koi common prefix nahi hai.

Lesson complete?

Trie samajh aa gaya✓ Ab Segment Tree dekhte hain � range queries ke liye bahut powerful data structure!