How many vertices does a complete binary tree of height 1, 2, and d has?The depth of a vertex in a rooted tree is defined to be the number of edges on the unique path to the root. The height of a...

How many vertices does a complete binary tree of height 1, 2, and d has?

The depth of a vertex in a rooted tree is defined to be the number of edges on the unique path to the root. The height of a rooted tree is the maximum of the depths of its vertices. A binary tree is complete if it is full and all its leaves have the same depth.

Asked on by araion

1 Answer | Add Yours

Top Answer

lfryerda's profile pic

lfryerda | High School Teacher | (Level 2) Educator

Posted on

Every node of a complete binary tree has two branches and a single parent, except for the root node which has no parent (but still two branches).  This means at every level, the number of vertices has doubled over the number of vertices at the higher level, which ends up being `2^{l-1}` where l the level.

To find the total number of vertices, we need to add up the number of each level.  That is,

`T=1+2^1+2^2+cdots+2^{d-1}`   geometric series

`={2^d-1}/{2-1}`

`=2^d-1`

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

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

Ask a question