Binary Tree Index

Computer Science Level 2

The binary tree above has a height of 2 (the number of rows excluding the top) and can index 4 items on the bottom row as shown.

What's the minimum height in a binary tree such that it can index 1000 items on the bottom row?

10 11 12 13

1 solution

Jason Dyer Staff
Oct 11, 2016

Each row multiplies the number of nodes in the previous node by 2.

At a height of 0, there is $2^0 = 1$ node.

At a height of 1, there are $2^1 = 2$ nodes.

At a height of 2 (as shown in the picture), there are $2^2 = 4$ nodes.

In general, for a height of $n ,$ there are $2^n$ nodes in the bottom row. Since $2^{10} = 1024 > 1000$ the minimum height needed is 10.