How many vertices does a complete binary tree of height D have? Please do a proof by induction.How would you solve this using induction?    geometric series The total number of vertices in a...

How many vertices does a complete binary tree of height D have? Please do a proof by induction.

How would you solve this using induction?

   geometric series

The total number of vertices in a complete binary tree is and the trees of height 1 have 1 vertex, and trees of height 2 have 3 vertices.

1 Answer | Add Yours

mlehuzzah's profile pic

mlehuzzah | Student, Graduate | (Level 1) Associate Educator

Posted on

First, I think your definition of height not be standard.  I think the tree with just a root (1 vertex) is considered to have height 0, and the tree with a root and 2 leaves (3 vertices) is considered to have height 1.  I will use your definition of height, this is just an fyi.

First, by induction, we show that a complete binary tree has `2^(D-1)` leaves:

The base case:

as you point out, the height 1 tree has 1 vertex; `2^(1-1)=2^0 = 1`

Thus this is true for the base case.

Now the induction step:

Assume that a complete tree of height ` `D has `2^(D-1)` leaves, and we want to show that a complete tree of height D+1 has
`2^(D-1+1) = 2^D` leaves

In the height D tree, we had (by assumption) `2^(D-1)` leaves.  Now, to each of those leaves, we give exactly two children, which become the new leaves.  This gives `2*2^(D-1) = 2^D` leaves in the height D+1 tree.  So the induction step is proven.


SO:

a complete binary tree of height D has `2^(D-1)` leaves.




Now, to figure out the pattern for the number of vertices in a complete tree of height D, maybe try drawing the first few.  You get:

height    #vertices
1    1
2    3
3    7
4    15
5    31

What you might notice is that the relationship looks like:

vertices = `2^D-1`

So that is the relationship we will try to prove by induction.





Base case:

The tree of height 1 has 1 vertex:

`1=2^1-1` so the statement is true for the base case.


Induction Step:

Assume that a tree of height D has `2^D-1` vertices.  We want to use this assumption to show that a tree of height D+1 has `2^(D+1)-1` vertices.

To get from a complete tree of height D to a complete tree of height D+1, we attach 2 children to each of the leaves in the height D tree.  So we take the number of vertices in a height-D tree and add to it the number of leaves in a height-(D+1) tree.  This is the number of vertices in a height-(D+1) tree.

We know the number of vertices in a height-D tree is `2^D-1` (this was our induction assumption)
We know the number of leaves in a height-(D+1) tree is `2^D`
So the total number of vertices in a height-(D+1) tree is
`2^D-1+2^D = 2(2^D)-1 = 2^(D+1)-1`

So we proved the induction step.



SO: The number of vertices in a complete binary tree of height D is `2^D-1`


We’ve answered 318,928 questions. We can answer yours, too.

Ask a question