# 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$$<$$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$$ )

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$.
• @AkhilNadhPC $\{x\in T|x<a\} \cup \{x\in T|x>b\}$ – aaaaajack Jan 11 '17 at 7:05