Hash tables are NOT O(1). You just failed the job interview.
tptacek, what do you think they are?
tptacek, what do you think they are?
Worst case search for a radix trie is always O(k); radix tries don't require balancing.
Where did you go to school?
Where I went to school, we were taught not to compare the worst case behavior of one structure to the average of another. We were also taught not to confuse binary trees with red-black trees.
Agreed. However the original poster said binary tree, a specific structure whose worse case behavior is O(n) just like a hash table.
They didn't say binary search tree (which as you observe may refer to one of several possible structures).