Build a tree where each node represents a character. Each node has up to 26 children (one per letter) and a flag indicating if a word ends here.
Insert: Walk down the trie, creating nodes for missing characters. Mark the final node as a word ending.
Search: Walk down the trie following the characters. Return true only if you reach the end and the node is marked as a word ending.
StartsWith: Walk down the trie following the prefix characters. Return true if you can follow the entire prefix (regardless of word-ending flag).