Tries, also known as prefix-trees or crit-bit trees, have existed for over 40 years but are still relatively unknown.
What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
getRandom() should pick a "random" element from your data structure, and should not be predictable (for instance always picking the "first" element from your DS)