In: Computer Science
a tree is binary, if every node has at most two children nodes. prove that the maximum of nodes in a binary tree of height h is 2^(h+1)-1
We want to show that maximum of nodes in a binary tree of height h is 2(h+1)-1.
We want to find the maximum number of nodes of binary tree,which means that the binary tree is completed.
For level 1 of complete binary tree,number of nodes=1=20
for level 2,number of nodes=2=21
for level 3,number of nodes =4=22
for level 4,number of nodes=8=23
.
.
.
for level h,number of nodes=2h
Total number of nodes in a complete binary tree will be,
=20+21+22+24+.....+2h
= from the equation of sum of geometrical progression= ,where a is the first term,r is the common ratio and n is the number of terms.
= 2(h+1)-1
Hence proved.