This problem is concerned with range queries on a balanced binary search tree T whose keys are distinct $($no two keys in T are equal$).$The range query is a generalization of the ordinary search operation. The range of a range

query on T is defined by a pair $[$xl$,$ xr$],$ where xl and xr are two numbers and xl xr$.$ Note that

xl and xr may not be the keys in T$.$

You know that T can support the ordinary search, insert, and delete operations, each

in O$($log n$)$ time, where n is the number of nodes of T$.$ You are asked to design an algorithm to

efficiently perform the range queries, that is$,$ in each range query, you are given a range $[$xl$,$ xr$],$

and your algorithm should report all keys x stored in T such that xl x xr$.$ Your algorithm

should run in O$($k $+$ log n$)$ time, where k is the number of keys of T in the range $[$xl$,$ xr$].$ In

addition, it is required that all keys in $[$xl$,$ xr$]$ be reported in a sorted order.

Note that you are not supposed to augment the tree for this problem. Please make sure you give

the pseudocode for your algorithm.

Such an algorithm of O$($k $+$log n$)$ time is an output$-$sensitive algorithm because the

runtime $($i$.$e$.,$ O$($k $+$ log n$))$ is a function of the output size k$.$ As an application of the range

queries, suppose that the keys of T are student scores in an exam. A range query like $[70,80]$

would report all scores in the range in sorted order.