4.9k views

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$

edited | 4.9k views

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

2h+1-1

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

I think H(n) represents an AVL tree with height n, having the minimum number of nodes.

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

If you can plz post a pic of your solution. Take an AVL tree with height = 4. and there must be 15 nodes in it. I say there are 12 nodes at max.
isn't complete binary tree is an example of AVL tree?
Draw a complete binary tree with 7 nodes you get a height of 2 at max. and an AVL tree can get it upto 3. try to draw that.

you have written "Max Nodes in an AVL tree with height n is H(n) = H(n-1) + H(n-2) + 1."  So I am saying change "Max nodes" to "minimum no. of nodes", because this recurrence is used to find the maximum height of an AVL tree with n nodes, not maximum no. of nodes with height h.

1. Formula 1(a stricter one) :
$h < 1.475 \times log_2(n(h)) - 1.475$
According to this formula, I get
$h < 1.475 \times log_2(7)-1.475$
$h<\color{red}{2.665}$

2. Formula 2:
The second one is rough estimate and it is taken from Goodrich's book:
$h < 2 \times log_2(n(h)) + 2$
According to this formula, I get
$h < 2 \times log_2(7) + 2$
$h<\color{red}{7.61}$

So with these different answers, I don't get what should I infer.  The proof of both these formulae looks good. But still they yield significantly different answers. Also the first one is more closet to the answer we get by using recurrence, while the second formula gives solution deviating a lot from the recurrence solution.

Gate_Keeda has written Minimum Nodes in an AVL tree with height n is H(n) = H(n-1) + H(n-2) + 1. right???

This makes the height as 3: