Implement Trie (Prefix Tree) - Solution & Explanation

Problem Overview: Design a Trie (Prefix Tree) that supports three operations: insert(word), search(word), and startsWith(prefix). The structure must efficiently store strings and allow fast prefix lookups.

Approach 1: Native Trie with Fixed Array Children (O(L) time per operation, O(N * A) space)

This approach builds a classic Trie where each node stores an array of 26 pointers (for lowercase English letters) and a boolean flag indicating the end of a word. During insert, iterate through each character and create nodes when a child pointer is missing. For search and startsWith, traverse the same path and verify whether nodes exist for each character. Each operation processes characters sequentially, giving O(L) time where L is the word length, while space grows with the total number of nodes allocated across all words.

The key advantage is constant-time child access using array indexing (index = char - 'a'). This removes hashing overhead and keeps traversal predictable. It is the most common implementation in interviews because the structure directly demonstrates understanding of prefix trees.

Approach 2: Trie Using Hash Maps for Children (O(L) time per operation, O(N) space)

Instead of a fixed array, each node stores its children in a hash table or dictionary keyed by characters. When inserting a word, check if the current character exists in the map; if not, allocate a new node and store it. Search and prefix queries follow the same traversal logic but perform hash lookups instead of array indexing.

This version trades slightly slower lookups for improved memory efficiency when the alphabet is large or sparse. Only existing edges are stored, which reduces unused pointers. In languages like Python or JavaScript, map-based nodes also produce cleaner implementations since dictionaries handle dynamic keys naturally.

Both implementations rely on the same core idea: a prefix tree shares common prefixes between words. Instead of storing full strings repeatedly, characters form paths from the root to terminal nodes. Prefix queries simply stop traversal early and confirm that the path exists.

Recommended for interviews: The fixed-array Trie is typically expected. It demonstrates clear understanding of prefix trees, direct character indexing, and efficient traversal. Showing the map-based version proves deeper design awareness—especially when discussing trade‑offs between memory usage and constant-time access. Both highlight how string problems can benefit from specialized data structures built around prefixes.