Question

2. A complete binary tree is defined inductively as follows. A complete binary tree of height 0 consists of 1 node which is the root. A complete binary tree of height h +1 consists of two complete binary trees of height h whose roots are connected to a new root. Let T be a complete binary tree of height h. Prove that the number of leaves of the tree is 2" and the size of the tree (number of nodes in T) is 2h+1 – 1.

Answer 1

******************************************************************************************
Please Upvote the answer as it matters to me a lot :)
*****************************************************************************************
As HOMEWORKLIB RULES expert answering guidelines,Experts are supposed to answer only certain number of questions/sub-parts in a post.Please raise the remaining as a new question as HOMEWORKLIB RULES guidelines.
******************************************************************************************

let us suppose a complete binary tree of height x has y nodes

then no of leaves if the binary tree of height x+1 = 2*y (since each leaf node now becomes internal node and produces exactly 2 leaf nodes)

we know that the height of 0 will have 1 leaf node

height of 1 will have 1*2 leaf nodes

height of 2 will have 1*2*2 leaf nodes

height of 3 will have 1*2*2*2 leaf nodes

...................................

...................................

..................................

height of h will have 1*2*2*.....*2(2^h) leaf nodes