The Gateway to Computer Science Excellence
0 votes
what is the maximum possible hight of AVL tree with 54 node?

is there any general method to solve this question?
in DS by (425 points) | 156 views

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

1 Answer

0 votes
Best answer
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
by Active (2.8k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,168 answers
94,047 users