Is the median of a binary max-heap always a leaf node?

Question

If I have a binary max-heap (a nearly complete binary tree with the max-heap property), then will the median always be a leaf node? I've found some examples where this is the case, but haven't found a counter example -- though this isn't enough for me to formally prove it so far.

i.e. for the set of values {1,2,3,4,5} where the median is [3], the tree would be:

    5  
   / \
  4   [3]
 / \
2   1

So in this case, the median is a leaf node.

Answer 1

No, it's not always a leaf node. You can easily rearrange your example to prove this. Another valid max heap using those same items is:

    5  
   / \
 [3]  4
 / \
2   1

Consider a full max-heap of 7 items:

       7
   6     [4]
 1   5  3   2

That is a valid max-heap. The largest item is at the root, and all of the child nodes are smaller than their parents.

It should be clear from these two examples that you can't assume that the median in a heap is always a leaf node.