Number of nodes in a binary tree of height h
- June 12, 2012
- Posted by: Kamal Rawat
- Category: Algorithms
Given a binary tree of height ‘h’. What will be the minimum and maximum number of nodes in the tree?
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
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