Register

GATE CSE 2017 Set 1 | Question: 6

• edited by
16,724 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
User Avatar

10 Answers

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..
User Avatar
1 votes
1 votes

for max height in Binary search should in skewed form. Therefore  max height will be n-1=15-1=14

for min-height binary search tree (or any binary tree) = lowerbound(log2 n)

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

38 votes
38 votes
7 answers
6
Arjun asked Feb 14, 2017
18,832 views
GATE CSE 2017 Set 1 | Question: 20
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
User Avatar
25 votes
25 votes
3 answers
9
makhdoom ghaya asked Feb 12, 2015
7,342 views
GATE CSE 2015 Set 1 | Question: 10
Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)? $3, 5, 7, 8, 15, 19, 25$ $5, 8, 9, 12, 10, 15, 25$ $2, 7, 10, 8, 14, 16, 20$ $4, 6, 7, 9, 18, 20, 25$ I and IV only II and III only II and IV only II only
Which of the following is/are correct in order traversal sequence(s) of binary search tree(s)?$3, 5, 7, 8, 15, 19, 25$$5, 8, 9, 12, 10, 15, 25$$2, 7, 10, 8, 14, 16, 20$$4...
User Avatar
Link Copied!