in DS edited by
43,165 views
39 votes
39 votes

What is the maximum height of any AVL-tree with $7$ nodes? Assume that the height of a tree with a single node is $0$.

  1. $2$
  2. $3$
  3. $4$
  4. $5$
in DS edited by
43.2k views

3 Comments

i think maximum number of node present in AVL tree in which root consider as height 0 is 

2h+1-1

4
4
Not just in avl, in any binary tree it is right!
5
5
This gives minimum height not maximum .
0
0

5 Answers

83 votes
83 votes
Best answer

Answer is B.
With $1$ node height is $0$.

Max height will come when each level contain min nodes. 

Minimum Nodes in an AVL tree with height $n$ is $H(n) = H(n-1) + H(n-2) + 1$.
$H(0) = 1$.
$H(1) = 2$
$H(2) = H(1) + H(0) + 1 = 2+1+1 = 4$
$H(3) = H(2) + H(1) +1 = 4+2+1 = 7$.


So, the max height with $7$ nodes is $3$.

edited by

4 Comments

Nice explanation .
0
0
1
1

@ Vikrant Singh

because maximum no. of nodes an AVL tree with height can have is 2n-1

 

Yes that’s correct H(n) is representing minimum no. of nodes needed AVL tree for height n. But maximum no. of nodes an AVL tree contains of height n is $2^{n+1}-1$ if n levels are required then your saying is correct.

0
0
6 votes
6 votes

option b

1 vote
1 vote

AVL tree is binary search tree with additional property that difference between height of left sub-tree and right sub-tree of any node can’t be more than 1

  • If there are n nodes in AVL tree, minimum height of AVL tree is floor(log2n).
  • If there are n nodes in AVL tree, maximum height can’t exceed 1.44*log2n.

1.44*log7 = 4 so maximum height can’t exceed 4

so to get max height if we keep Minimum number of nodes at each level there is chance to get maximum height

eg:at 1st level 2 elements one at right other at left(because we should satisfy avl property) similarly others at 2nd level 2 elements at 3rd level 2 elements

eg:

1 vote
1 vote
Maximum height of AVL tree can be =1.44* log (base 2) n

Hence 1.44 *log base 2 (7)=2.8 = 3

Hence option B

2 Comments

1.44 *log2(7) is 4.04 and not 2.8
1
1
This formula is only valid if n is large like 1000 nodes,500 nodes like this.for very small n it may not work properly.
0
0
Answer:

Related questions