How to find minimum height of a binary tree, if you know its numbers of nodes?

Question

Let n be the number of nodes of a binary tree, then what will be the general functional term to find out the minimum height of the binary tree?

I think it will be n=floor(log2(n))+1. But, I think, I'm wrong.

Solution 1

From Binary Tree Height:

If you have N elements, the minimum height of a binary tree will be log2(N)+1.

Solution 2

See remember this concept that

for height to be minimum you will have to give each level, the maximum no of nodes it can accomodate

so for a tree of height h, maximum no of nodes that can be accomodated by the tree in total = 2^(h+1)-1, so n<=2^(h+1)-1
After solving you will get
h>=log(n+1)base2 -1
Now for deciding floor or ceil of log, think like this

If my logn is coming 3.56.. then it means that till height 3 each level is fully consumed, last level is not completely filled. So as the definition of height says that it is the longest path from root to the leaf, so in height we will include that last level also.

Therefore ceil will be preferred over floor.With this approach you can also find for m-ary tree.

Solution 3

Try proving this by induction. Type of a binary tree is inductive, with two constructors:

• Leaf(v)
• Node(Tree,Tree)

You can now use structural induction to show the minimum height of a binary tree. To get minimum height you have a complete binary tree. This is a binary tree such that, for any subtree, it's children have the same height. (This basically means that if you draw the tree out you don't see any "holes.") So assume you have this type of tree, we want to prove its height is floor(log_2(n)) + 1. You can prove this slightly simpler by turning it around and saying: say I have a tree with height floor(log_2(n))+1, prove it will have at most n nodes. You can prove this by structural induction over the constructors.

Comments

[Kristopher Micinski]

why the downvote? I don't see anything incorrect with this answer. Please explain if so so that it may be corrected.

[KMC]

This solution not going to work unless you have full tree. Even with full tree, this requires round down. Try with 3 nodes with all nodes having only left or right child.