avl tree

Question

what is the maximum possible hight of AVL tree with 54 node?

is there any general method to solve this question?

Comments

maximum height possible when you construct height with minimum number of nodes.

Minimum number of nodes required to form a AVL tree with height h = 1 + Nodes(h-1) + Nodes (h-2)

let root height = 0

height-0 = 1 node required

height-1 = 2 node required

height-2 = 4 node required

height-3 = 7 node required

height-4 = 12 node required

height-5 = 20 node required

height-6 = 33 node required

height-7 = 54 node required ===> Maximum height possible with 54 node is height-7 when root height = 0

Answer 1

Intutively to obtain maximum height, you'll try to make tree unbalanced and in case of AVL trees height difference of only one is allowed between left and right nodes.

So if a maximum height tree is constructed using n nodes has height h, then one of it's child should have height h-1 and other should have h-2 and they both should also be maximum possible height AVL tree. This gives us a recursive equation.

if n(x) represents number of nodes reqd. to create an AVL tree with max. height x, then we can write,

$n(h) = 1 + n(h-1) + n(h-2)$

base conditions, $n(0) = 1, n(1)= 2$

Now you can find, n(0), n(1), n(2),.. and check where 54 falls