问题描述:

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

您可能感兴趣的文章：

- iphone - Push Notifications in Mavericks iOS Simulator
- How to bypass firewall for RSYNC with SSH tunneling and corkscrew Proxy
- php - PDO cannot insert records
- ruby on rails - Console working, server not
- php - wkhtmltopdf change the default size parameter from mm to pixels
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**