6.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 | 6.9k views
+1

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

2h+1-1

+1
Not just in avl, in any binary tree it is right!

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
+4

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

+2
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.
0
isn't complete binary tree is an example of AVL tree?
+1
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.
+1

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.

0

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.

0

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

+6

This makes the height as 3:

0
Nice explanation .

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
2