# Height of AVL Tree

I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am concerned about their difference. Doesn't AVL guarantee maximal-minimal height difference to be 1?

The repository from which I got the code

• It should guarantee that, so it might be that what you have found is a more relaxed version of some sort of self balancing tree. Dec 13, 2021 at 11:29
• I dont think that its an AVL tree, cause theorietical bounds for min/max heights with n nodes are logn and 1.44*logn which turns out to be the range 20-28 in this case. I agree that it might be a relaxed version of some self balancing tree. Maybe you could share the link to its implementation so that one can understand it better. Dec 13, 2021 at 12:54
• @RinkeshP: Provided a link to the repo. Thanks Dec 13, 2021 at 14:39
• No, AVL does not require max-min height difference to be <=1 on all paths. It does require that, for each node, (max height of left subtree) and (max height of the right subtree) are at most 1 unit apart. Example: en.wikipedia.org/wiki/Fibonacci_number#/media/…
– chi
Dec 13, 2021 at 16:07
• @Chi This very useful. If you could provide this as an answer(with the "max height" emphasized) I'll gladly mark it so. Dec 13, 2021 at 16:42