I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way:

Each new node is inserted via percolate up. This means that each new node must be created at the next available child. What I mean by this is that children are filled level-down, and left to right. For example, the following heap:

   / \
  1   2

would have to have been built in this order: 0, 1, 2. (The numbers are just indexes, they give no indication of the actual data held in that node.)

This has two important implications:

  1. There can exist no node on level $k+1$ without level $k$ being completely filled

  2. Because children are built left to right, there can be no "empty spaces" between the nodes on level $k+1$, or situations like the following:

       / \
      1   2
     / \   \
    3  4    6

(This would be an illegal heap by my definition.) Thus, a good way to think of this heap is an array implementation of a heap, where there can't be any "jumps" in indeces of the array.

So, I was thinking induction would probably be a good way to do this... Perhaps something having to deal with even an odd cases for n. For example, some induction using the fact that even heaps built in this fashion must have an internal node with one child for an even n, and no such nodes for an odd n. Ideas?

  • $\begingroup$ @DaveClarke: Not quite; the linked question is the result of a misunderstanding on us editors' parts left there for reference. $\endgroup$
    – Raphael
    Mar 28, 2012 at 6:45
  • $\begingroup$ Have you tried induction over node number resp. number of insertions? $\endgroup$
    – Raphael
    Mar 28, 2012 at 7:17
  • $\begingroup$ @DaveClarke: Why? It is a valid question in itself, imho. $\endgroup$
    – Raphael
    Mar 28, 2012 at 9:03
  • $\begingroup$ BTW, the question has nothing to do with heaps. The claim holds for any complete binary tree $\endgroup$
    – Ran G.
    Mar 29, 2012 at 6:07

2 Answers 2


If I get your question correctly, the obtained heap is just an ordered binary-tree, where in ordered I mean that the $k$th level can only be occupied after the $k-1$ level has been completely filled, and each level is occupied from left to right, without skipping.

Then the proof goes like this.

  1. A perfect tree of depth $k$ has exactly $2^{k+1}-1$ nodes.
  2. Assume that the heap reaches depth $k$. Thus
    1. up to level $k-1$ the tree is perfect (and has $2^k-1$ nodes there)
    2. on the last level, there are exactly $n-2^k+1$ nodes, which are all leaves.
  3. Each leaf on the $k$th level has a parent. Moreover, each two consecutive leaves have the same father (maybe except for the last node, whose father has only one child)
  4. Thus, out of the $2^{k-1}$ nodes at level $k-1$, $\left\lceil \frac{n-2^{k}+1}{2} \right\rceil$ are parents, and the rest $2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$ are leaves.
  5. The total amount of leaves is $$n-2^k+1 + 2^{k-1} - \left\lceil\frac{n-2^{k}+1}{2}\right\rceil$$ Which gives you what you need.
  • 1
    $\begingroup$ Note that full are different from complete are different from perfect binary trees. Unfortunate, ambiguous and inconsistent choice of words there, but what can you do about it. I guess sticking to Wikipedia's definition makes sense, as most will look there first? $\endgroup$
    – Raphael
    Mar 28, 2012 at 6:49
  • $\begingroup$ Oh, wow, I didn't even know these terms. Thanks for pointing this out. $\endgroup$
    – Ran G.
    Mar 28, 2012 at 7:22
  • $\begingroup$ "up to level k−1 the tree is perfect (and has 2^k − 1 nodes there)" and "Thus, out of the 2^(k−1) nodes at level k−1" seem to be conflicting statements, or am I missing something? $\endgroup$
    – adrian h.
    Aug 12, 2016 at 10:36
  • $\begingroup$ @adrianh. ($2^k-1$) nodes in the entire subtree, $2^{k-1}$ nodes only on the last level (thus in the entire subtree there are $2^{k-1}+2^{k-2}+...$ nodes.) $\endgroup$
    – Ran G.
    Aug 12, 2016 at 14:11
  • 1
    $\begingroup$ @SachinBahukhandi 2 children -> 1 parent. 1 (last) children -> 1 parent. Then the number of parents is half the children, maybe plus one because of the last (single) child. $\endgroup$
    – Ran G.
    Apr 11, 2020 at 16:20

Here's a simpler logical proof.

Last leaf is $n^{th}$ index. Its parent is at index $\lfloor{n/2}\rfloor$ and similarly, there is no element such that its parent is ($\lfloor n/2 +1\rfloor)^{th}$ element. Thus leaves are indexed from $\lfloor{n/2}\rfloor$ +1 to n.

Hence, total number of leaves = n- $\lfloor(n/2)\rfloor$ = $\lceil(n/2)\rceil$.

  • 2
    $\begingroup$ Quite intuitive and clear explanation. Thanks. $\endgroup$
    – whitehat
    Nov 18, 2015 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.