How can I calculate the ideal height of a tree structure?

When I have this tree I know the height is `4`.

There's a formula that says that the ideal height of a tree is `2 ^ height - 1` but that doesn't make sense to me (since it would be `15`).

Well, first of all, that formula applies only to binary trees. Second, the ideal number of nodes in the tree will be `2^height-1`. For a saturated binary tree of height `4`, the number of nodes will be `15`.

That formula is for the maximum number of nodes that can be included in a binary tree of that height. Assuming you want the tree to be as shallow as possible, you want to know the minimum height of such a tree given the number of nodes. So you simply invert:

``````nodes = 2^height - 1
``````

to get

``````height = log2(nodes + 1)
``````

rounded up.

Height of the tree is the maximum height among all the nodes in the tree. Now say you have a tree

``````                                         1
/   \
2    3
/  \  / \
4  5  6  7
``````

the height of the tree is 3(since all path lengths are same so lets say 1-2-5 is maximum) now as there are three levels so no of node at each level

``````                                          1         =2^0
/   \
2    3      =2^1
/  \  / \
4  5  6  7    =2^2
``````

total =2^0 +2^1+2^2= clearly its a gp with sum 2^3-1 ,hence the number of nodes =2^height-1 if you talk about levels(as they start from 0) no of nodes= 2^(level+1)-1

Top