# The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. 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?

• 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?
– D.W.
Mar 15, 2017 at 16:45
• 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. Mar 15, 2017 at 20:13

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.