In order to find the recurrence function of The Height in Heap, the following figure is drawn.

enter image description here

Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have the height of Left subtree as log in base 3/2?

Question 2: it is stated that:
"for a complete binary tree to have the maximum height the last level should be half full."
i don't grasp the logic behind this line.why?

  • 1
    $\begingroup$ Welcome to CS.SE! Where are you quoting/excerpting this from? Can you provide additional context? It looks like you are taking an excerpt from some discussion, but we are forced to guess what the surrounding material is. Can you provide the full reasoning? What problem are they solving? How does this picture relate? $\endgroup$
    – D.W.
    Commented Mar 15, 2017 at 16:45
  • 1
    $\begingroup$ For Q2, I think that maybe height is being mixed up with something else. The height of a tree is the longest distance from the root to a leaf node. It will be the same regardless of if a complete tree is full or not. $\endgroup$
    – ryuu9187
    Commented Mar 15, 2017 at 20:13
  • $\begingroup$ This diagram is particularly unfriendly because it attempts to draw generalities (height as a function of n) from a particular example, and we're left to guess which parts of the example should "survive" the generalisation process. They keep the 1/3 and 2/3 in the general formula, even though those seem to be numbers very specific to this example and not holding up at all in general. Perhaps with the context (ie with surrounding text explaining what was meant) it might make more sense. $\endgroup$
    – Stef
    Commented Jan 27 at 11:14

1 Answer 1


You are asking several question. I will only answer one. If you start with a set of size $n$ and you repeatedly reduce it to at most $rn$ elements, then after $t$ steps, you will have at most $r^tn$ elements. If $r^tn < 1$, then after $t$ steps you will have no elements. This happens for $t > \log_{1/r} n$. This explains where $\log_{3/2} n$ and $\log_2 n$ come from.


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.