The Gateway to Computer Science Excellence

+21 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$*.*

- $4$ and $15$ respectively.
- $3$ and $14$ respectively.
- $4$ and $14$ respectively.
- $3$ and $15$ respectively.

+12 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$

+23 votes

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

Ans:**B**) $3,14$

+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)

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)

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

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

52,215 questions

60,022 answers

201,249 comments

94,709 users