How many vertices does a complete binary tree of height 1 have?

Question

1. How many vertices does a complete binary tree of height 1 has?

2. Height 2?

3. Height d?

Any hints on how to start to tackle these set of questions?

Answer 1

For definitions of height and complete binary tree, see Binary Trees. It is worth noting that the definition of complete binary tree may allow for more leaves to be added at the lowest level. Strictly speaking it is a perfect binary tree has all leaves present at the lowest level: you need to clarify whether your question is really referring to a perfect binary tree.

To find the number of vertices in a perfect binary tree of height $h$, on paper

• draw a perfect binary tree of height 1, and count the number of vertices
• draw a perfect binary tree of height 2, and count the number of vertices
• and so on...
• ... and see if you can spot a pattern.

You may find the sum of a geometric series useful in turning the pattern into a formula.

If you do need to find the number of vertices in a not necessarily perfect, complete binary tree, this is at most the number of vertices in a perfect binary tree of the same height, and has to be greater than the number of vertices in a perfect binary tree of one less height.