Trie Operations

Type the letters `a-p-p` into a search box and the autocomplete dropdown produces `apple`, `application`, `apply`, and `appoint` before you finish the next keystroke. The data structure doing that work is a **Trie** (or prefix tree), where every stored word is a path from root to a marked node and every shared prefix is shared in memory exactly once. This lesson covers the trie node layout (a `children` map plus an `isEndOfWord` flag), `insert`, `search`, and `startsWith` operations that all run in `O(m)` for a query of length `m` (independent of how many words the trie holds), and a `delete` that has to be careful not to break paths used by other words. You will also analyze the space behavior, including when a trie wins over a hash set (prefix queries, lexicographic enumeration) and when it loses (memory-tight workloads with no prefix structure to exploit). In **Hash Map (Dictionary) Basics**, you used hashing to answer 'have I seen this exact key' in `O(1)`; a trie answers a strictly richer question (any prefix lookup) by trading `O(1)` exact-match for `O(m)` traversal. **Trees: Binary Tree Fundamentals** introduced the recursive child-pointer pattern, and a trie generalizes it from two children per node to one child per alphabet symbol. With a trie in your toolkit, the curriculum moves on to graph and hash extensions that solve a different family of problems built on the same node-and-edge thinking.