edited by
16,618 views
33 votes
33 votes

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

  1. $4$ and $15$ respectively.
  2. $3$ and $14$ respectively.
  3. $4$ and $14$ respectively.
  4. $3$ and $15$ respectively.
edited by

10 Answers

Best answer
22 votes
22 votes

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$

edited by
27 votes
27 votes

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$

edited by
12 votes
12 votes

please do correct me if I m wrong

Answer:

Related questions

38 votes
38 votes
7 answers
1
Arjun asked Feb 14, 2017
18,659 views
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
25 votes
25 votes
3 answers
4