Implement Trie (Prefix Tree)

Implement Trie class:

• insert(word): Inserts string word.
• search(word): Returns true if string word is in the trie.
• startsWith(prefix): Returns true if there is a previously inserted string having prefix.

Watch how insert creates new nodes only when necessary, and search traverses existing paths.

1. Node Structure: Each node contains a map/array of size 26 (for 'a'-'z') and a boolean isEnd.
2. Insert: Traverse down; create nodes if missing. Mark last node as isEnd.
3. Search: Traverse down; if node missing -> return false. At end, return node.isEnd.
4. StartsWith: Traverse down; if node missing -> return false. If loop finishes, return true.