Trie (Prefix Tree)

⏱ Time: O(L) per operation💾 Space: O(N * L)

A tree-like data structure used to store a dynamic set or associative array where the keys are usually strings. Efficient for prefix-based searches and auto-completion.

🎯 When to Use

  • ✓Autocomplete and typeahead search
  • ✓Spell checkers
  • ✓Prefix matching IP routing

📝 Pseudocode

Trie (Prefix Tree) TemplateO(L) per operation
1class TrieNode:
2  children = {}
3  isEndOfWord = false
4
5function insert(word):
6  node = root
7  for char in word:
8    if char not in node.children:
9      node.children[char] = new TrieNode()
10    node = node.children[char]
11  node.isEndOfWord = true

🏢 Real-World Use Cases

Google
Search Autocomplete

Suggesting search queries in real-time as users type based on frequency and prefix matching in a Trie.

💡 Practice Problems (1)

1.Implement Trie (Prefix Tree)Medium
→
← Back to Patterns