The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
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$

 

asked in DS by Veteran (69k points)
edited by | 4.9k views

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

2h+1-1

1 Answer

+40 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$.

answered by Veteran (19.8k points)
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.

there are two formulae given on this page: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-height.html

  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:



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

33,705 questions
40,252 answers
114,344 comments
38,862 users