Is the height of a binary tree log2(n)

user_10368147 0
Viewed 929

Lets say we have an array with the length of n=7, the height of the tree should be 2. I wouldn't count the height by the number of rows but connections between them. (I think that because in the heapsort algorithm the Siftdown Method says that the last row as a height of 0 it can travel and the row before can travel height of 1, so 2 rows in a tree would allow height 1 to travel.)

So to get the height I would calculate log2(allNodesInTheBottomRow) which is (n+1)/2.

Is log2((n+1)/2) correct?.

Here, an example:

enter image description here

binary-tree logarithm algorithm
1 Answers

In general it is not true that the height of a binary tree is O(log n). Note that in the following image, both of these trees are valid binary trees:

The image on the right is just an *unbalanced* binary tree

Note that the tree on the right fulfills the property that the right child is larger than the root and is itself the root of a binary tree.

I think what you mean to say is that a balanced binary tree has height O(log n). Note that the canonical definition of a balanced binary tree is a the binary tree on the given set of elements where the height is minimal (or in many cases, close to minimal - a constant factor away). It is straightforward to make the intuitive observation that this happens when each row is fully saturated (i.e. the tree is complete or almost complete).

Note that when the tree is fully saturated, the first row has 1 element, the second row has 2 elements, and the ith row has 2^(i-1) elements. As a result, we have that if there are n elements, that n = 2^(log n). This means that there are O(log n) rows as needed.

If you are looking for a precise function to compute the height rather than just an O(log n) bound, you simply round n up to the nearest power of 2 and then compute the log of that. For example, if n=7, the nearest power of 2 is 8 and log(8) = 3 as needed. You can subtract by 1 at the end depending on your definition of height.

user_20935790
Related