问题描述:

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`

).

Can someone please explain?

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