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

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 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:

clip_image002[7]

clip_image002[9]

  • 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:

clip_image002[11]

  • 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:

clip_image002[15]

  • 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:

clip_image002[17]

  • Please note that the value of ‘log2x’ is much than ‘x’.


More Information:

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


References:

Book:

Advertisements

2 thoughts on “Data Structures: Key points about a Binary Tree – Part 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s