Find Number of elements X in the Tree that lie between a and b

Question

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$<$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,

1. $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)$

2. $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$ )

Answer 1

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$.