GATE CSE 2017 Set 1 | Question: 6

Question

Let $T$ be a binary search tree with $15$ nodes. The minimum and maximum possible heights of $T$ are:

Note: The height of a tree with a single node is $0$.

• A. $4$ and $15$ respectively.
• B. $3$ and $14$ respectively.
• C. $4$ and $14$ respectively.
• D. $3$ and $15$ respectively.

Answer 1

The maximum height of a binary search tree will be when the tree is fully skewed

Maximum height  $= n - 1 = 15 – 1 = 14$

The minimum height of a binary search tree will be when the tree is full.

Minimum height  $= \log_2( n + 1 ) – 1 =  \log_2( 15 + 1 ) – 1 = \log_2( 16 ) – 1 = 4 - 1 = 3$

Correct Answer: $B$

Comments

min ht. should  be floor[logn] right?

because for 14 nodes the min ht of tree is also 3 ,which we can get by floor[logn]

but not by log(n+1)-1.

---

@Pranavpurkar

Max nodes for height ‘h’ $ (n) = 2^{h+1} -1$

Hence, Min Height = $ log(n+1) – 1$

---

Abhrajyoti00

then  it must be ceil of that value for minimum height.

---

Yes @Pranavpurkar, it will be $\lceil(log(n+1))\rceil$

Answer 2

Min height of a binary tree is given by $\log _{2}(n+1)-1=4-1=3$

max height of the binary tree is $n - 1$ (skewed binary tree$= 15 - 1 =14$

Ans:B) $3,14$

Answer 3

B) 3,14 .

Worst case : skewed

Answer 4

please do correct me if I m wrong