Answer

A trie stores words by decomposing them into individual characters along paths. Each node can have up to k children (one per alphabet character). In the worst case, you need O(n * m * k) space because you may create O(n * m) nodes total (n words of length m), and each node maintains k pointers for potential children. This is worse than a hash map for sparse data but provides fast prefix-based lookups.