The Gateway to Computer Science Excellence
+19 votes
3.8k views

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.
in DS by Veteran (422k points)
edited by | 3.8k views

9 Answers

+10 votes
Best answer

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$

by Boss (10.6k points)
edited by
+22 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$

by Loyal (7.8k points)
edited by
+11 votes
B) 3,14 .

Worst case : skewed
by Active (2k points)
+9 votes

please do correct me if I m wrong

by Active (1.9k points)
+8 votes
Height will be maximum when the BINARY SEARCH TREE is completely skewed

example for an ASCENDING order sequence of numbers say {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} hence maximum height will be

14

height will be minimum when tree is maximally packed that is every level is filled completely before moing to next level...

in that case

level 1->1 node

level 2-> 2 node

level 3-> 4 node

level 4-> 8 nodes

so in 4 level total nodes are 1+2+4+8=15

so min height is 3

hence correct answer is

option (B)
by Active (3.4k points)
Answer:

Related questions

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
50,662 questions
56,122 answers
193,626 comments
93,025 users