Saturday, June 29, 2013

Number of nodes in a complete binary tree

How many nodes are there in a full complete binary tree of level 6?

a) 40             b) 31               c) 127               d) 128

A binary tree's level starts at 0,  a full complete binary tree has 2^i nodes at level i. At level 0 there is 1 node, at level 1 there are 2 nodes and  it goes on.

There are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 = 2 ^ (6+1) - 1 = 2^7 - 1 = 127 nodes.

A level is also called the height of the binary tree. In a full complete binary tree of height 'h' there are 2^(h+1) - 1 nodes.

2^0+ 2^1+ 2^2 + 2^3+...................... +2^h = 2^(h+1) - 1

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children. A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are filled in left to right order.



In a complete binary tree of height 'h' there can be [2^h  2^(h+1) - 1] nodes.  A complete binary tree can have 2^h minimum number nodes or 2^(h+1)-1 maximum number of nodes.

In a complete binary tree of height 2, there can be 4 minimum number of nodes and 7 maximum number of nodes. 

Share your thoughts in the comments below, to make me describe the blog post  even better and do recommend the post if you found the content helpful!!!

6 comments:

  1. On the other hand, along with software package the idea becomes easier and you will help make a great deal of trading eventually. It can be probable you could end up creating 80% involving income on your own investment decision in a mere an hour or so. Consequently, let's pretend people commence with $100 on 1 PM HOURS, then you could log off of along with $180 on 2 PM HOURS! binary

    ReplyDelete
  2. Hello GATE Aspirants

    The rising trend of books for gate cse preparation have fascinated number of prospects to ice GATE coaching centre as they enjoy the spirit of visual learning and live discussions with the prominent people from the industry and even the engineers employed by the society.

    ReplyDelete
  3. this is too vague explanation also I m very much confused about the exact height of a binary tree

    ReplyDelete

  4. Find trendy technology stock photos in HD and tens of millions of different royalty-loose stock photographs, illustrations and vectors within the Shutterstock series.


    Random Email Generator
    Black light app
    Temp mail
    Terrarium TV App
    tik tok
    ERP software

    ReplyDelete