1
$\begingroup$

I have an AVL tree with height h. I understand how to get h $\thickapprox$ 1.440 log N. However, I can't figure out how to calculate the minimum depth of a leaf node from root. I tried constructing a recursive formula where d = 1 + min(dL, dR) where dL and dR are the depths of the left and right subtree of the root. But can't get a solution of this. Can anyone help me out here?

$\endgroup$
  • $\begingroup$ Have you tried to use the AVL invariant, namely $|d_L - d_R| \leq 1$? $\endgroup$ – Yuval Filmus Sep 9 at 9:14
  • 2
    $\begingroup$ Try a proof by induction. $\endgroup$ – Yuval Filmus Sep 9 at 9:15
1
$\begingroup$

Denote by $d(h)$ the minimum height of a leaf in an AVL tree of height $h$. One subtree of the root necessarily has height $h-1$, and the other one has height either $h-2$ or $h-1$ by the defining property of AVL trees. Therefore $$ d(h) = \min(d(h-1),d(h-2)) + 1. $$ Also, one checks that $d(0) = d(1) = 0$ (if one measures height as the maximum number of edges in a root-to-leaf path). The recurrence makes it clear that $d$ is monotone, and so $d(h) = d(h-2) + 1$. From here it's easy to calculate $d(h) = \lfloor h/2 \rfloor$.

$\endgroup$
  • $\begingroup$ Yes, I did just like this after you commented "Try a proof by induction". Thanks a lot. Hope this question comes in exam on Friday! $\endgroup$ – Siladittya Sep 9 at 11:15
  • $\begingroup$ Actually I was also thinking of another approach where I take as induction hypothesis P(h) => An AVL tree with height h has depth of leaf node at least ceil(h/2) and then remove the root of the AVL tree. Thus we get two trees T1 and T2 with height (h-1) and (h-2) or (h-1) respectively. By induction hypothesis, d(T2) is atleast ceil((h-2)/2). Thus, depth of leaf node in T = depth of leaf node in T2 + 1 = ceil((h-2)/2) + 1 = ceil(h/2), which was our induction hypothesis in the first place. Is this a valid proof?? $\endgroup$ – Siladittya Sep 9 at 11:22
  • $\begingroup$ It's essentially the same argument, only expressed a bit differently. $\endgroup$ – Yuval Filmus Sep 9 at 11:25
  • $\begingroup$ So, this is a valid proof, right? Actually I don't understand the meaning of "The recurrence makes it clear that d is monotone." Can you explain it briefly? $\endgroup$ – Siladittya Sep 9 at 11:28
  • $\begingroup$ This is something you need to prove by induction, but the proof is pretty simple. $\endgroup$ – Yuval Filmus Sep 9 at 11:29

Your Answer

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

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