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$
2
  • $\begingroup$ Have you tried to use the AVL invariant, namely $|d_L - d_R| \leq 1$? $\endgroup$ Sep 9 '19 at 9:14
  • 2
    $\begingroup$ Try a proof by induction. $\endgroup$ Sep 9 '19 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$
6
  • $\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 '19 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 '19 at 11:22
  • $\begingroup$ It's essentially the same argument, only expressed a bit differently. $\endgroup$ Sep 9 '19 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 '19 at 11:28
  • $\begingroup$ This is something you need to prove by induction, but the proof is pretty simple. $\endgroup$ Sep 9 '19 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.