# How to prove that in an AVL tree with height h, the depth of every leaf node is at least $\lceil h/2 \rceil$

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?

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

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$$.