The height of a tree is the length of the longest path from root to leaf. What…
2021
The height of a tree is the length of the longest path from root to leaf. What is the maximum and minimum number of nodes in a binary tree of height n?
- A.
2n+1−1,n+1
- B.
2n-1−1,n-1
- C.
2n,n+1
- D.
2n-1 , 1
Attempted by 548 students.
Show answer & explanation
Correct answer: A
To find the maximum and minimum number of nodes in a binary tree of height n, consider the following:
Maximum Nodes: A binary tree of height n has maximum nodes when it is a complete binary tree, i.e., all levels are completely filled. The number of nodes at level i is 2^i. So, total nodes = 2^0 + 2^1 + ... + 2^n = 2^(n+1) - 1.
Minimum Nodes: A binary tree of height n has minimum nodes when it is a skewed tree (all nodes are in a single path). In this case, there is one node at each level from 0 to n, so total nodes = n + 1.
Thus, the maximum number of nodes is 2^(n+1) - 1 and the minimum is n + 1.