Suppose there is a balanced binary search tree with n nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node.
Now, given two elements a and b, such that a$<$b, we want to find the number of elements x in the tree that lie between a and b, that is, $a≤x≤b$ This can be done with (choose the best solution).
- O(logn) comparisons and O(logn) additions.
- O(logn) comparisons but no further additions.
- O(√n) comparisons but O(logn) additions.
- O(logn) comparisons but a constant number of additions.
- O(n) comparisons and O(n) additions, using depth-first- search.
Now there are two possibilities,
$b$ can be in the right subtree of $a$
We simply search for b, in the right subtree of aa and at each step we add the number of elements in the left subtree +1 (BST being balanced, this can be retrieved from the depth of the node without any finding method), if we are moving right and simply 1 if we are moving left. When we find $b$, this sum will give as the required number of elements. This requires $O(logn)$
$b$ can be in the right subtree of any of the parents of $a$.
For the second case also we do the same method. But first we find the common ancestor of $a$ and $b$ (possible in $O(logn)$- say $p$ and also count the no. of nodes in the right subtree of each node from $a$ to $p$ excluding $p$. Now, from $p$ to $a$ we proceed the counting as in the earlier case when $b$ was in the subtree at $a$. So, in the worst case we have to do $O(logn)$ additions
How to make use of the nuber count more efficiently than this ?
Answer is given by my professor is
O(logn) comparisons but a constant number of additions.
Please elaborate the efficient approach using neat diagrams for clear cut understanding for both (when $b$ is right subtree of $a$ and $b$ is right subtree of parent of $a$ )