Do BSTs actually allow search in logN time?

Time to search a BST is limited by its height. Each step goes down one level. Therefore, worst case: O(Height).

Question: is Height O(logN)? Unfortunately no!

However, most trees are not degenerate.

For N random values: expected Height = 1.4(log(N+1)).

Problem comes from nodes where one subtree is much deeper than the other. What if we required that they be the same height (within 1)?

Answer: Height would be O(logN), so search would be O(logN) too.

Trees with this property are called Balanced Trees.