Jun 122012
 

Given a binary tree of height ‘h’. What will be the minimum and maximum number of nodes in the tree?

Answer:

The number of nodes are not the same for all the trees of a particular height. For example if the height of the tree is 2 then its structure can be

    A
     \ 
      B

or,

    A
   / \ 
  B   C

Both having different number of nodes.

The number of nodes will be minimum if the tree has exactly one node at each level. and it will be maximum if the tree is a Complete Binary Tree.

Minimum Number of Nodes in a Binary tree of height h = h

Maximum Number of Nodes in a Binary tree of height h = 2h-1

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)