If I'm given a tree with "$k$" keys, or "$n$" nodes and I need to find the minimal / maximal height of the tree, I know that I have to split it into two cases:

$i$. The tree is full

$ii$. The tree is not full

For case $i$ I know that given an "$M$" (max number of children), let's say $M=4$ and number of nodes, let's say "$n$" if I need to find the minimal height each node will have the maximum amout of children (in this case 4). So the calculation will look like

$\sum_{i=0}^{h}4^{i}=\frac{4^{\left(h+1\right)}-1}{3}=n\ \ \ ➜\ \ \ 4^{\left(h+1\right)}-1=3n\ \ \ ➜\ \ \ 4^{h}=\frac{3n\ \ +1}{4}\ \ ➜\ \ \ h=\log_{4}\left(\frac{3n\ \ +1}{4}\right)$

But now it gets confusing to be.. what if the right hand side is not an integer, do we use floor or do we use ceiling, and which ever it is than why? and how does it affect the equation and the explicit value of h?

For case $ii$ in my understanding it is only relevant if we are given the number of keys, and in this case I don't quiet get the procedure to finding "$h$"..


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.