Homework Help

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

user profile pic

araion | Student, Undergraduate | eNoter

Posted August 12, 2012 at 7:12 PM via web

dislike 1 like

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.

1 Answer | Add Yours

Top Answer

user profile pic

lfryerda | High School Teacher | (Level 2) Educator

Posted August 12, 2012 at 11:15 PM (Answer #1)

dislike 1 like

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.

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes