In my book, I read the following statement:
Suppose that the tree is a binary search tree, then:
If the tree contains all values from 1 to n exactly once, and n is the root of the tree, then the height of the tree cannot be log2(n) (rounded up)
Why does this statement hold?
If n is the root, that means that all of the remaining (n-1) elements are on one side of the tree. Thus, the height of the tree is at least d = 1 + log2(n-1)
Little algebra:
log2(n-1) + 1 = log2(n-1) + log2(2) = log2(2(n-1)) > log2(n) for n > 2
So the tree that has n at the root cannot attain height log2(n) if it has more than 2 elements.
Regarding the rouned up part:
Let n=17, 17 in the root. Remaining 16 elements comprise a perfect binary tree of height 4, so total tree depth is 5, which contradicts the claim that the depth can't be ceil(log2(17)) == 5.