In Big-O notation for tree structures: Why do some sources refer to O(logN) and some to O(h)?

Question

In researching complexity for any algorithm that traverses a binary search tree, I see two different ways to express the same thing:

Version #1: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(h).

Version #2: The traversal algorithm at worst case compares once per height of the tree; therefore complexity is O(logN).

It seems to me that the same logic is at work, yet different authors use either logN or h. Can someone explain to me why this is the case?

Answer 1

O(h) would refer to a binary tree that is sorted but not balanced

O(logn) would refer to a tree that is sorted and balanced

Answer 2

If your binary tree is balanced so that every node has exactly two child nodes, then the number of nodes in the tree will be exactly N = 2^h − 1, so the height is the logarithm of the number of elements (and similarly for any complete n-ary tree).

An arbitrary, unconstrained tree may look totally different, though; for instance, it could just have one node at every level, so N = h in that case. So the height is the more general measure, as it relates to actual comparisons, but under the additional assumption of balance you can express the height as the logarithm of the number of elements.