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.


*

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, sonAfter solving you will geth>=log(n+1)base2 -1Now 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.

You are watching: Minimum height of a binary tree

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


*

From Binary Tree Height:

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


*

*

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.


*

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid

Asking for help, clarification, or responding to other answers.Making statements based on opinion; back them up with references or personal experience.

See more: All Postal Code For Montego Bay Jamaica, All Postal Codes In Montego Bay

To learn more, see our tips on writing great answers.


Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy


Not the answer you're looking for? Browse other questions tagged data-structures tree computer-science binary-tree discrete-mathematics or ask your own question.


site design / logo © 2021 Stack Exchange Inc; user contributions licensed under cc by-sa. rev2021.10.1.40358


Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.