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.


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.