Find Number of elements X in the Tree that lie between a and b Question
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$&lt;$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(log⁡n)  comparisons and O(logn) additions.
O(log⁡n) comparisons but no further additions.
O(√n) comparisons but O(log⁡n) additions.
O(log⁡n) comparisons but a constant number of additions.
O(n) comparisons and O(n) additions, using depth-first- search.

My Approach
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(log⁡n)$- 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(log⁡n)$ additions
How to make use of the nuber count more efficiently than this ?
Answer is given by my professor is

O(log⁡n) 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$ )
We may assume without loss of generality that the lowest common ancestor of $a$ and $b$ is the root. Let $S = \{x \in T| key(a) \le x \le key(b) \} $. Observe that $|S| = |T| - |\bar{S}|$, and that $|\bar{S}|$ is the sum of the sizes of the left subtree of $a$ and of the right subtree of $b$.