ISRO2020-20

Question

The minimum height of an AVL tree with $n$ nodes is

• A. $\text{Ceil } (\log_2(n+1))$
• B. $1.44\ \log_2n$
• C. $\text{Floor } (\log_2(n+1))$
• D. $1.64\ \log_2n$

Comments

https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

acoording to this option c match

 

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;\textbf{(c)}$

$\text{Minimum height} =\color{magenta}{\mathbf{\bigg\lfloor  \log_2 \left ( n + 1  \right  )\bigg \rfloor}}$

$\text{Maximum height} =\color{blue}{\mathbf{1.44\log_2n}}$

Comments

Answer is C.

---

Answer should be c .

As if we consider number of nodes= 8.

Minimum height of AVL tree will be 3.

floor(log(8+1)) = 3.

Whereas ceil(log(8+1)) = 4, which is wrong.

Please check.

---

@SuvasishDutta

Say for 3 nodes, minimum and maximum both height should be 1, right?

but with C) it is showing height should be 2. Then how is it matching?

---

@srestha

it will not match with option a either.

can you match?

consider those examples which will differentiate the options

---

Again say for 7 nodes, minimum height 2, but accoring to the formula minimum height 3??

Formula should match with every example. right?? not with only one example.

---

Option A is correct , because 1 node is at height 1 take any case for floor or ceil it is 1 only ,the actual answer start from 2 node where 2 node, minimum height is 2 but via floor it gives 1 which is wrong hence A is most appropriate answer.

---

minimum height of AVL tree with n nodes is = ceil[ log(n+1) ] -1

option C is not matching when there is 3 nodes or 7 nodes.

By default height of root node is 0.

---

Right, thanks!

---

isro has given c opton.

---

@MRINMOY_HALDER

Can u read my comment once? it is not a) and not even C) matching with real examples, right?

---

yes. No one matches when #nodes are complete.(3, 7, 15, 31.......)

---

Here  floor( log(3+1))=floor(log4)=floor(2)=1

We have to take floor value ..

if  you dont like this than you can also use this log(n+1)-1

both  of them are same..

---

What about 1.44logn?

---

It is maxheight 

1.44log(3)=1.44*2=2.88=floor(2.88)=1(if indexing starts from 0)

If indexing starts from 1 than max height should be 2.than we have to take floor(1.44log(n))+1. 

Actually I referred this link.https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

---

actually the unnecessarily added $+1$ for trying to make the answer different from the standard  $\log \mathbf n$ and failed miserably to justify now. :D

Answer 2

If there are n nodes in AVL tree, minimum height of AVL tree is floor(log2n). Option C

Explanation : Please refer the link below

https://www.geeksforgeeks.org/practice-questions-height-balancedavl-tree/

Comments

For $7$ nodes, minimum height = $2$.

Options B and D give fractional heights. So, they’re wrong.

Options A and C give $3$.

 

So, the question assumes the root to be at height $1$.

Rewriting: For $7$ nodes, maximum height = $3$.

For $6$ nodes, it will still be $3$.

 

Only Option A satisfies this.

 

The answer is also Option A in the official answer key.

---

Edit: Meant to comment on the question, lol. Not on this answer.

Answer 3

As we know there are minimum of 4 node in height 2 in avo tree because minimum height is h(no of node-1) and h(no of node -2)

So putting n=4 in all option we will obtain h=2 in floor(log2(n+1))