26 votes 26 votes The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height $h$ is: $2^h -1$ $2^{h-1} -1$ $2^{h+1} -1$ $2^{h+1}$ DS gatecse-2007 data-structures binary-tree easy + – Kathleen asked Sep 21, 2014 Kathleen 25.7k views answer comment Share Follow See 1 comment See all 1 1 comment reply vupadhayayx86 commented Aug 8, 2018 reply Follow Share If height of tree tree start with 0 then? I think answer depends on whether height start from zero or 1. Correct me if I am wrong 1 votes 1 votes Please log in or register to add a comment.
Best answer 44 votes 44 votes $2^{h+1} - 1$ just try this taking a small complete binary never try to remember these formulae as remembering formulae is an overhead try to take examples in such cases. Correct Answer: $C$ Bhagirathi answered Sep 22, 2014 edited May 4, 2019 by Naveen Kumar 3 Bhagirathi comment Share Follow See all 4 Comments See all 4 4 Comments reply Ayush Upadhyaya commented Sep 4, 2018 reply Follow Share The maximum number of node will occur when each level is completely filled from height 0 to h. At each height, we have a maximum of $2^h$ nodes $\sum_{k=0}^{h}2^k=2^0+2^1+2^2+....+2^h=\frac{2^{h+1}-1}{2-1}=2^{h+1}-1$ nodes. 20 votes 20 votes jatin khachane 1 commented Dec 26, 2018 reply Follow Share @Ayush Upadhyaya If height is defined as number of nodes from root to leaf then it will be 2^h - 1 right ? 0 votes 0 votes PRANAV M commented Oct 18, 2019 reply Follow Share But it didnt even mentioned it is complete binary tree???, 0 votes 0 votes Gaganjot _Kaur commented Nov 12, 2019 reply Follow Share @PRANAV M Question is asking about the maximum number of nodes for a given height,so number of nodes will be maximum (i.e. tree is most dense) when it is a full binary tree. Also keep in mind the difference between Full and Complete binary tree, they are not the same. 0 votes 0 votes Please log in or register to add a comment.
10 votes 10 votes At maximum tree is given as above So maximum height = 2 (15 - > 10 -> 8) or other all are same height Put h = 2 in option and find number of nodes A- 22 -1 = 3 wrong B- 21-1 = 1 wrong C- 23-1 = 7 correct D- 23 = 8 wrong SO option C is correct option Rishi yadav answered Oct 5, 2017 Rishi yadav comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes height H=0 ( only root node ) , no of node N=1=20 H=1 , N=21 ... so on total =20 +21+22+.......2H =2H+1-1 Ans is C Gate Ranker18 answered Aug 21, 2017 Gate Ranker18 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes =2$^0$+2$^1$+2$^2$+...+2$^h$ this a gp =2$^h$$^+$$^1$-1 Musa answered Jul 7, 2020 Musa comment Share Follow See all 0 reply Please log in or register to add a comment.