So definition of the complete binary tree is that ” Every node in the tree will have either no children or two children.”
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.
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,
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*2d-1= 2^(d+1)-1.
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,
log2 n= log2 2^d
log2 n= d log2 2= d
So, d= log2 n
This means that depth of a complete binary tree is at least .