So long as he's apparently requesting this sort of thing, why not use a Patricia trie instead of a TST? Typical use-cases would probably yield a lot of single-

So long as he's apparently requesting this sort of thing, why not use a Patricia trie instead of a TST? Typical use-cases would probably yield a lot of single-child nodes in a TST, which a Patricia trie would eliminate. There would probably be a good amount of memory savings, and the only additional code complexity would be a strcmp() (edit: which doesn't increase the algorithmic complexity, since you'd be doing those comparisons anyway). Using a TST is probably fine; it just looks like this problem cries out for a Patricia trie.