1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But how does it will solve in O(log n) comparisions and constant additions ? $\endgroup$ – Pc_ Jan 11 '17 at 3:41
  • $\begingroup$ @AkhilNadhPC $\{x\in T|x<a\} \cup \{x\in T|x>b\}$ $\endgroup$ – aaaaajack Jan 11 '17 at 7:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.