**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_{2} n= log_{2} 2^d

log_{2} n= d log_{2} 2= d

So, d= log_{2} n

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