General Reference Material | Answers to Binary Tree Questions

Answers to Binary Tree Questions

For the most part we do not give "formal" proofs of these results. Some of the answers are simple enough that you can guess the correct answer quickly by trying an example or two. For most of the others we give an informal justification which should nevertheless convince you of the validity of the answer. Come to think of it, isn't that a "proof"? ... :) In at least one case, a proof would take us some distance afield, so we merely state the answer, but give some other related results to show how interesting the answer really is.

Answers to questions about binary trees

What is the maximum number of levels in a binary tree containing n nodes?
Answer: A few examples should convince you the answer here is n, the number of nodes in a degenerate binary tree of n nodes (the one that's as long and skinny as it can be, by going straight down to the left or right from the root).
What is the maximum level number in a binary tree containing n nodes?
Answer: If you think about the answer to the previous question, then it should be clear that the answer here is n-1, the maximum level number of in a degenerate binary tree of n nodes.
What is the maximum number of nodes at level k in a binary tree?
Answer: A few examples should convince you the answer here is 2^k: At level 0 the answer is 2⁰ = 1, at level 1 the answer is 2¹ = 2, at level 2 the answer is 2² = 4, at level 3 the answer is 2³ = 8, and so on ...
What is the maximum number of nodes in a binary tree containing k levels? Here is an alternate form of the same question: How many nodes are in a full binary tree with k levels?
Answer: Getting this answer requires you to remember the (high school) formula for the sum of a geometric series, but once you have that and have looked at a few examples, you should easily deduce that the answer is 2^k-1. For a short proof see here.
What is the minimum possible number of levels in a binary tree of n nodes?
Answer: Here you need to be comfortable with the log function (with base 2) and the floor function. If so, then by looking at a few examples you may be able to conclude that the answer is floor(log₂n)+1. Or, we can reason as follows.

Suppose we construct a larger and larger binary tree by numbering each node as we add it to the tree, and that we proceed to build the tree as illustrated in the following figure:
```
                               1
                      2                  3
                  4       5          6       7
               8     9 10   11    12   13 14   15
             16  17 ...
   
```
The first thing we should note is that on level k the values, reading from left to right, are 2^k, 2^k+1, 2^k+2, ..., 2^k+1-1. That is, we have 2^k <= n < 2^k+1 for any n on that level. If we now take the logarithm to the base 2 of each term in this continued inequality, we have k <= log₂n < k+1, from which it follows that k = floor(log₂n). In other words, the depth of such a tree with n nodes is floor(log₂n) and the number of levels is floor(log₂n)+1. [This follows since the number of levels in a tree is always one greater than the maximum level number.] And, since the way we built the tree makes it a complete binary tree (and it's therefore as "short and bushy" as possible), this will be the minimum depth and minimum number of levels.
Can you draw all the binary trees containing exactly n nodes (at least for small values of n, say 1, 2, 3, 4, and 5)? Or, can you draw all the binary trees having a certain number of nodes and a certain depth? [Example: Can you draw all binary trees with 4 nodes and having depth 3?]
Answer: The answer is, "Yes, you can, if you're careful!" And see the answer to the following question so that you know how many you're looking for in each case.
How many different binary trees containing exactly n nodes are there?
Answer: This one is not so easy. The answer is, of course, the general answer to the question immediately above, if we just want to know how many there are, without bothering to actually draw them. The answer is the Catalan number, which is another one of those quantities that crops up here, there and everywhere in nature, in seemingly unrelated situations. Its value is given by Cat(n) = (2n)!/((n+1)!n!). See here for some pictures and additional info. For further information, Google "Catalan numbers".