I did a quick re-implementation [0] taking these ideas into account. It also avoids assuming anything about inputs except iterating the key type and moves most functionality into Node to support more use cases.

[0] https://github.com/codr7/stash/blob/master/trie.cpp