Medium
Trie node count: shared prefixes vs. disjoint strings
You insert n = 100,000 strings, each of length L = 50, into an uncompressed trie (one child pointer per character; no compression of single-child chains). The alphabet is large enough that 100,000 distinct characters are available at any position. Case A: all strings share the same 49-character prefix and differ only in their last character. Case B: no two strings share even a single character of prefix. Approximately how many trie nodes does each case create?
5 of 46 in Data Structures & Algorithms