It seems that golang doesn't support co- and contravariance or any neat tricks to get general interfaces work. Shame on that. The test code that compares the two trie implementations passes now.