# Data Structures: Key points about a Binary Tree – Part 2

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 2l node at level ‘l’..
• A complete binary tree of depth ‘d’ is the binary tree of depth ‘d’ that contains exactly 2l 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 2d leaves and therefore 2d-1 non-leaf 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, ‘logb 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 ‘log2x’ is much than ‘x’.

Part 3 will shed light on ‘almost complete binary trees’.

References:

Book:

1. bittib says: