How many vertices does a complete binary tree of height 1 has?
Height 2?
Height d?
Any hints on how to start to tackle these set of questions?
Asked
Active
Viewed 2,819 times
-4
-
2Start by looking up the definitions of "complete binary tree" and "height". – Chris Eagle Jul 21 '13 at 16:37
-
Okay, so a binary tree with a height of one would have three rows. I binary tree with a height of 2 would have 3 rows and a binary tree of height d would have (d+1) rows. What should I look in to next? I understand vertices, but I am just referring to the general set? If so, I think height 1 would have 2 vertices, height 2 would have 6 vertices, but I do not know about height d. I would imagine it would be d to some power. – Natasha Jul 21 '13 at 16:52
-
Work induction from your base cases, @Natasha. – Torsten Hĕrculĕ Cärlemän Jul 21 '13 at 17:09
-
A perfect binary tree of height $1$ has two levels, not three: it has a root with two daughter vertices. – Brian M. Scott Jul 21 '13 at 21:13
1 Answers
4
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.
