edited by
16,620 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

10 votes
10 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)
1 votes
1 votes
Height of a binary search tree is minimum if it is a complete binary search tree..

Minimum height is lg(n+1)-1 as given n = 15 hence on solving We get lg(15+1) -1 which is equal to 3.

In the worst case the binary search tree will be skewed hence the max height will be 14.

Correct me if I am wrong.

I am new to this platform so please guide me further..
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