This article is an extension to article ‘Data Structures: Key points about a Binary Tree – Part 1’. Please refer the part 1 blog post in case you find some of terms used in this article quite confusing.
Complete Binary Tree:

A complete binary tree of depth ‘d’ is a strictly binary tree all of whose leaves are at level ‘d’.
Example of a complete binary tree of depth 3:
Key points about a Complete Binary Tree:

If the binary tree has ‘m’ nodes at level ‘l’, it contains at most ‘2m’ nodes at level ‘l+1’.

Since a binary tree can contain at most one node at level 0 (i.e. the root node), it can contain at most 2^{l} node at level ‘l’.^{.}

A complete binary tree of depth ‘d’ is the binary tree of depth ‘d’ that contains exactly 2^{l} nodes at each level between ‘0’ and ‘d’.^{.}
Computing total number nodes in a Complete Binary Tree:

The total number of nodes in a complete binary tree of depth ‘d’, denoted by ‘tn’ is equal to the sum of the total number of nodes at each level between ‘0’ and ‘d’. Thus, we can deduce the formula:

The above equation represents the total number of nodes in a complete binary tree at level ‘d’. By mathematical induction, the above equation is equal to:

All leaves of a complete binary tree are at level ‘d’, hence the tree contains 2^{d} leaves and therefore 2^{d1} nonleaf nodes.^{.}

If the total number of nodes, tn, in a complete binary tree is known, we can compute the depth, d, using the equation:

The significance of the above equation is that, ‘d’ is one less than the number of times ‘2’ must be multiplied by itself to reach ‘tn+1’.
Further reduction of the equation:

To further reduce the equation, we should know that in mathematics, ‘log_{b }x’ is defined as the number of times ‘b’ must be multiplied to reach ‘x’.

Using the above mathematical concept, we may say that in a complete binary tree, depth ‘d’ can be obtained using the formula:

Please note that the value of ‘log_{2}x’ is much than ‘x’.
More Information:
Part 3 will shed light on ‘almost complete binary trees’.
References:
Book:

Data Structures Using C and C++ (2nd Edition) by Yedidyah Langsam, Moshe J. Augenstein, Aaron M. Tenenbaum. Link to the book at Amazon: http://www.amazon.com/DataStructuresUsingYedidyahLangsam/dp/0130369977
Advertisements
The definition of complete binary tree is incorrect. The one you explained is more like a full binary tree or strict binary tree. You can refer here http://en.wikipedia.org/wiki/Binary_tree