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.
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2017 Set 1 · Q6
Time
Select one answerSingle correct
Solution
Official answer: B) 3 and 14 respectively
Binary Search TreesGiven nodes and the height of a single node tree is :
Minimum Height (): The height is minimized when the tree is as balanced and full as possible. For height , the maximum number of nodes in a binary tree is:
For nodes:
Maximum Height (): The height is maximized when the binary search tree is completely skewed (degenerate into a linked list).
Therefore, the minimum and maximum possible heights are 3 and 14 respectively, corresponding to option (B).
Try the question first, then check your work.
Examiner trap
The minimum height corresponds to a complete/perfect binary tree (), and the maximum height corresponds to a skewed binary search tree ().
This Binary Search Trees previous year question is Q6 of the GATE CSE 2017 Set 1 paper. Find more GATE CSE PYQs on Binary Search Trees in Programming and Data Structures, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Binary Search Trees PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Binary Search Trees has 21 GATE CSE PYQs across 17 papers from 2011 to 2026. 8 of them are 1-mark MCQs like this one, and it is the only one in GATE CSE 2017 Set 1.
How GATE tests Binary Search TreesIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.