data structures

Question

1. What is the minimum and maximum height of a binary tree with 511 nodes. Solve this problem without drawing the tree. Make sure to show your work.

Answer 1

The tallest tree you can make just has one node on every level, so with 511 nodes, the highest you can get is 511 levels. The most nodes a tree can have on a single level is 2^N-1 where N is the level. This gives 1 node on the first level, 2 nodes on the second level, and so on. A neat trick to remember about powers of two is that the sum of the first N powers of 2 is 2^N+1-1. So if you sum up the nodes on the first N levels of a full binary tree, you get 2^N-1 nodes. 511=2⁹-1 So the shortest tree you can make with 511 nodes is 9 levels high.