Implement a prefix tree supporting insert(word), search(word), and startsWith(prefix).
Knowing the trie structure for prefix queries — the data structure behind autocomplete and spell-check.
A trie stores strings along character paths: each node holds a map of children keyed by the next character plus an isEnd flag marking where a complete word terminates. insert walks the word, creating nodes as needed, and sets isEnd on the last node. search walks the word and returns node.isEnd. startsWith walks the prefix and returns true if the whole path exists (regardless of isEnd). Signal: 'prefix', 'autocomplete', 'dictionary of words sharing prefixes', or 'word search on a board' → trie. Each operation is O(L) in the word length and independent of how many words are stored, versus O(n·L) to scan every word.
Autocomplete / typeahead, spell-check, prefix matching, IP routing, and word-search backtracking.
insert / search / startsWith O(L); space O(total characters)