Editor">
Editor Staff asked 5 months ago
Editor Staff asked 5 months 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 5 months ago
Editor Staff answered 5 months 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).
