What maximum difference in heights between the leafs of a AVL tree is possible?

Category: QuestionsWhat maximum difference in heights between the leafs of a AVL tree is possible?
Editor">Editor Staff asked 4 weeks ago

What maximum difference in heights between the leafs of a AVL tree is possible?
 
(a) log(n) where n is the number of nodes
 
(b) n where n is the number of nodes
 
(c) 0 or 1
 
(d) atmost 1
 
My doubt is from AVL Tree in section Binary Trees of Data Structures & Algorithms I
 
This question was posed to me in an interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

Correct choice is (a) log(n) where n is the number of nodes
 
To explain: At every level we can form a tree with difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since height of AVL tree is log(n).