TIFR CSE 2010 | Part B | Question: 26

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 \leq x \leq b$. This can be done with (choose the best solution).

• A. $O(\log n)$  comparisons and $O(\log n)$ additions.
• B. $O(\log n)$ comparisons but no further additions.
• C. $O \left (\sqrt{n} \right )$ comparisons but $O(\log  n)$ additions.
• D. $O(\log  n)$ comparisons but a constant number of additions.
• E. $O(n)$ comparisons and $O(n)$ additions, using depth-first- search.

Comments

Meaning of addition here is that nummber of elements that we are counting between a  and b

---

what is the correct answer then?

---

Here additions means the count of numbers(nodes) in the given range right, not the sum of the numbers in the range like the gate question. So how is it possible for the additions to be anything other than constant?

Answer 1

Number of comparisons will be O(logn) and additions will be constant.

Algorithm:

Step 1: First find out the lowest common ancestor of a and b.

            https://afteracademy.com/blog/lowest-common-ancestor-of-a-binary-tree

            O(logn)

Step 2: then find out the parent of both a and b using given algorithm

             https://www.geeksforgeeks.org/find-the-parent-of-a-node-in-the-given-binary-tree/

            O(logn)

Step 3: then use the given logic for finding out the number of additions required.

             N(p) : denotes no of children in its subtree ( it is stored in each node)

             P(p) : denotes parent of node p

             Z = no of nodes between [a,b]

             root is the lowest common ancestor of a and b.

             case 1 : if a is left child of its parent and b is right child of its parent

             Z= N(root) - ( N(a->left) + 1) - ( N(b->right) +1 ) +1

             case 2: a is right and b is right child of their parent

             Z = N(root) - ( N(a->left) + 1) - ( N( P(a) -> left ) +1 ) - ( N(b->right) +1 ) +1

             case 3 : if a is left child of its parent and b is left child of its parent

             Z= N(root) - ( N(a->left) + 1) - ( N(b->right) +1 ) - ( N ( P(b)->right ) +1)  +1

             case 4: a is right and b is left child of their parent

             Z = N(root) - ( N(a->left) + 1) - ( N( P(a) -> left ) +1 ) - ( N(b->right) +1 ) -

                   ( N ( P(b)->right ) +1)+1

            So only a constant no of additions required.