Answered Essay: Let T(d) be a complete balanced binary tree of depth d. T(1), shown in Fig. 2.24(a), has a root and two leaves. T(d) is obtained by attaching to ea

Solution:

a)

So definition of the complete binary tree is that ” Every node in the tree will have either no children or two children.”

Initial step:

So we have T(1) which has total 3 vertices out of which 1 is non-leaf and two are leaf nodes.

number of leaf node T(1)= 2^1= 2, which is true as shown in the picture.

number of non-leaf nodes T(1)= (2^d)-1= 2-1= 1, which is also true as shown in the picture.

Inductive Step:

Now with d= 2, our complete binary tree will look like this

Here we can see that the depth is 2 and total 7 nodes are present, out of which 3 nodes are non-leaf and 4 are leaf nodes.

T(2)= 2^2= 4 leaf nodes,

T(2)= (2^2)-1= 4-1= 3 non-leaf nodes,

Now,

T(3) has 15 nodes in which 8 are leaf nodes and 7 are non-leaf nodes.

We can observe the pattern here total number of nodes= 2^(d+1),

number of leaf nodes= 2^d and

number of non leaf nodes= 2^(d)-1

We can verify our result here by adding 2^(d)-1 and 2^(d) we should get 2^(d+1)-1

2^(d)-1+ 2^(d)= 2*2^d-1= 2^(d+1)-1.

b)

Now, a binary tree with n leaf and n-1 non-leaf nodes is a complete binary tree.

Let’s say the depth of this tree is d, then

n= 2^d as shown above,

Number of non-leaf nodes= Total number of nodes- number of leaf nodes= 2^(d+1)+ 2^d= 2(^d-1).

take log of both the sides,

log₂ n= log₂ 2^d

log₂ n= d log₂ 2= d

So, d= log₂ n

This means that depth of a complete binary tree is at least  .