Skip to content
GATEiit

GATE CSE 2020 Q51: Range reporting in a balanced BST with k results

Question

In a balanced binary search tree with nn elements, what is the worst case time complexity of reporting all elements in range [a,b][a, b]? Assume that the number of reported elements is kk.

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: B (official GATE 2020 final answer key)

Concept used: Range search walks two root-to-leaf paths and visits only subtrees fully inside the range.

First step: Search for aa and bb (height O(log⁡n)O(\log n) each), then do an in-order walk of the nodes between them.

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

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More Programming and Data Structures PYQs

PracticePractise Programming and Data Structures questions →Full paperAll GATE CSE 2020 questions →