Not sure if I follow. O(n log n) is worst than O(n). Insertions in a binary tree are expensive to keep it balanced.
If you use a set or hashmap assuming zero collisions, the look up is O(1). Then the bottke neck is in the string iteration. Right?
I've made the assumption that the binary tree was already built, it could've been done during compile time, for instance.
As for hashing functions, you could get away with an Array where the index is the code point for a given character.
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.