0
$\begingroup$

I'm wondering what's the answer of the following question:

What is the maximal difference between the depths of 2 leaves in an AVL tree?

Intuitively I think that it shouldn't exceed $log n$ but have no idea how to prove that. On the other hand, I saw multiple articles that claim the depth can become larger and larger without any formal proof (I always get a contradiction when trying to draw such trees)

I would really like if someone can explain me why it's correct\incorrect.

$\endgroup$
3

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.