# What is the maximum height of an AVL tree with p nodes?

Category: QuestionsWhat is the maximum height of an AVL tree with p nodes?
Editor">Editor Staff asked 5 months ago

What is the maximum height of an AVL tree with p nodes?

(a) p

(b) log(p)

(c) log(p)/2

(d) ^p⁄2

Origin of the question is AVL Tree topic in chapter Binary Trees of Data Structures & Algorithms I

This question was posed to me in an interview.

Editor">Editor Staff answered 5 months ago

Right option is (b) log(p)

Easy explanation – Consider height of tree to be ‘he’, then number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2). since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst case height.

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17

Notice: Trying to get property 'ID' of non-object in /home/fvckxqmi/public_html/wp-content/themes/blocksy/inc/single/single-helpers.php on line 17
Articles: 40702