Section Recap

Tries store strings with shared prefixes.

Each node represents a character, paths spell words. Core Operations:

• Insert: $O(L)$, create nodes along path
• Search: $O(L)$, follow path, check isEndOfWord
• Prefix: $O(L)$, like search but no end check

Patterns:

• Wildcard search with DFS
• Word dictionary with isEndOfWord flag
• Autocomplete with prefix traversal

When to Use: String prefix problems, dictionary lookups, autocomplete systems.

Time: $O(L)$ per operation. Space: $O(\Sigma \cdot N \cdot L)$ worst case.