The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
6.3k 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 (59.5k points)
edited by | 6.3k views
0

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

2h+1-1

2 Answers

+45 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 Boss (19.7k points)
edited by
+2

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.
0

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

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.

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???

+3

This makes the height as 3:

0
Gate Keeda does not have proper knowledge on this subject which is why he isn't responding to @Vikram.
0 votes

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:

answered by (85 points)


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

38,053 questions
45,543 answers
131,858 comments
48,881 users