Question

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.

Answer 1

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