GATE CSE 2021 Set 1 Q20: Time to pick a BST element smaller than the maximum
- Programming and Data Structures
- 1 mark
- MCQ
- −1/3 if wrong
Question
A binary search tree contains distinct elements. What is the time complexity of picking an element in that is smaller than the maximum element in ?
Try it: multiple choice: exactly one correct option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation
Answer: D (official GATE 2021 final answer key)
Concept used: Any element that is not the maximum will do; there is no need to find the maximum itself.
First step: Look at the root and one of its children: of two elements, the smaller one is certainly not the maximum.
Full step-by-step solution
Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.
Share this question
Source: official GATE 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key
More Programming and Data Structures PYQs
- 2026 Session 1 · Q23Non-leaf indices in a 1-indexed binary heap with n odd
- 2026 Session 1 · Q24Empty slots after linear-probing inserts with h(x) = (x+7) mod 11
- 2026 Session 1 · Q33Maximum height of a full binary tree with 23 nodes
- 2026 Session 1 · Q34Output of a C function with a shadowed block variable
- 2026 Session 1 · Q39Recursive length of a non-empty singly linked list
- 2026 Session 1 · Q40Third insertion that can never yield a complete BST of 1..15