Let $T$ be an AVL tree for storing a set of $n$ integers. Insertions and deletions in $T$ can hence be done in $O(\log n)$ time. Given two integers $a$ and $b, \: a < b$, you have to output nab, the number of integers in T whose value lies within $[a, b]$ in $O(\log n)$ time.
- For this purpose, what modification of $T$ and its insertion algorithm are required?
- Give a pseudo-code for computing $n_{ab}$.
