6,893 views
4 votes
4 votes
What is the max possible height of an AVL tree with 20 nodes?

a. 4

b.5

c.6

d.7

 

In my opinion answer should be b.5 because height of a tree with 1 node is 0 not 1, and recurrence relation to calculate maximum height of an AVL tree is:

T(H) = T(H-1) + T(H-2) + 1

1 Answer

Best answer
4 votes
4 votes

Maximum possible height is found by using as less number of nodes for a given height as possible..But at the same time we have to preserve the AVL property..

So we have the recurrence :

H(n) = H(n-1) + H(n-2) + 1   where H(n) indicates minimum no of nodes in a AVL tree of height n..

The base cases are : H(0) = 1 

                                H(1) = 2

So                            H(2) = 4

                                H(3)  = 7

                                H(4)  = 12

                                H(5)  = 20..

As we are to able to have 20 nodes within height 5,

Hence , maximum height of an AVL tree possible with 20 nodes = 5

selected

Related questions

2 votes
2 votes
1 answer
1
Akanksha Kesarwani asked Jan 15, 2016
8,022 views
What is the worst case possible height of an AVL tree??a. 2logn (Assume base of log is 2) b. 1.44log n (Assume base of log is 2)c. Depends upon implementationd. Thet...
3 votes
3 votes
1 answer
2
hrcule asked Jul 16, 2018
2,744 views
Let T be a binary search tree with n nodes and Sn be the average number of comparisons required for successful search and Un be the average number of comparison required ...
4 votes
4 votes
0 answers
3
AnilGoudar asked Jan 10, 2018
3,293 views
When node 50 will be deleted, what will be resultant AVL tree?
1 votes
1 votes
3 answers
4
slowpoke asked May 8, 2017
759 views
Which sequence If inserted in AVL tree will cause No adjustment in tree? a) 1 2 3 4 5 ...