Exams › GATE › Technical

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:

1. $2^h - 1$
2. $2^{h-1} - 1$
3. $2^{h+1} - 1$
4. $2^{h+1}$

Correct answer: $2^{h+1} - 1$

Solution

A binary tree has at most 1 node at level 0, 2 at level 1, 4 at level 2, and so on. Summing from level 0 to level $h$ gives $1+2+4+\cdots+2^h = 2^{h+1}-1$.

Related GATE Technical questions

• A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
• An array \([82, 101, 90, 11, 111, 75, 33, 131, 44, 93]\) is heapified. Which one of the following options represents the first three elements in the heapified array?
• Consider a binary min-heap containing 105 distinct elements. Let \(k\) be the index in the underlying array of the maximum element stored in the heap. The number of possible values of \(k\) is
• Which of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
• The maximum number of binary trees that can be formed with three unlabeled nodes is:
• The inorder and preorder traversals of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is

⚔️ Practice GATE Technical free + battle 1v1 →