edited by
43,283 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$
edited by

5 Answers

Best answer
83 votes
83 votes

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
1 votes
1 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:

1 votes
1 votes
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
Answer:

Related questions

3 votes
3 votes
2 answers
2
gatecse asked Dec 17, 2017
1,216 views
The $in$-$order$ and $pre$-$order$ traversal of a binary tree are $\text{d b e a f c g}$ and $\text{a b d e c f g}$ respectively.The $post$-$order$ traversal of a binary ...
7 votes
7 votes
2 answers
3
gatecse asked Dec 17, 2017
1,927 views
Match the following and choose the correct answer in the order $A, B,C$$\begin{array}{|ll|ll|} \hline \text{A.} & \text{Heap Construction} & \text{p.} & O(n\log n) \\\hli...
24 votes
24 votes
3 answers
4