Skip to interview prep
Apexed

192. What are the minimum and maximum numbers of nodes in a binary heap of height h?

EasyPriority queues & heaps

Technical
Show model answer

A binary heap is a complete binary tree, so every level except the last is full. Counting a single root as height 0, the fullest heap has all levels 0..h full: 1 + 2 + ... + 2^h = 2^(h+1) − 1 nodes.

The sparsest heap of height h has levels 0..h−1 full (2^h − 1 nodes) plus a single node on level h, giving 2^h nodes. So 2^h ≤ n ≤ 2^(h+1) − 1.

What are the minimum and maximum numbers of nodes in a binary heap of height h — Data structures & algorithms interview question — Apexed