Binary Tree Height

Question

I need a general formula to calculate the minimum height of the binary tree and the maximum height of the binary tree. (not the binary search tree)

Answer 1

Think about how the structure of the tree can change.

For example, if the tree is completely unbalanced then this is the worst case - each node will have exactly one child. In the best case, the tree is completed balanced, and each node has two children.

Since it sounds like homework, I'll leave it there.

Answer 2

The max height is n and the min height (IE a perfect binary tree) is the (log base 2( n + 1)) - 1

Answer 3

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

For a full binary tree, the maximum height will be N/2.

For a non-full binary tree, the maximum height will be N.