GATE CS 2014 Set 3 Q.49 (CS Q.39): Binary Trees, Binary Search Trees and Balanced Trees

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$ . Suppose there are $m$ such numbers in $T$ . If the tightest upper bound on the time to compute the sum is $O(n^a \log^b n + m^c \log^d n)$ , the value of $a + 10b + 100c + 1000d$ is _____.

Your answer

Official answer and solution

Official answer: 110
From: Official GATE 2014 answer key

Solution

Analyze the time complexity of a range query on a balanced binary search tree and match powers to find the required combination.

Range Query on a Balanced BST:
To sum all $m$ elements within the range $[L, H]$ in a balanced BST containing $n$ elements:
- Step 1: Search for the smallest key $\ge L$ in the tree. Because the tree is balanced (height $\Theta(\log n)$ ), this search takes $O(\log n)$ time.
- Step 2: From this starting node, perform an in-order traversal to retrieve each of the $m$ keys in range, stopping when a key $> H$ is encountered.
- The in-order traversal visits each of the $m$ reported nodes plus at most $O(\text{height}) = O(\log n)$ boundary nodes.
- Thus, the total time required is: $T(n, m) = O(\log n + m).$
Matching Coefficients:
We are given the tightest upper bound form:

$O(n^a \log^b n + m^c \log^d n).$

Matching this with $O(n^0 \log^1 n + m^1 \log^0 n)$ :
- $a = 0$
- $b = 1$
- $c = 1$
- $d = 0$
Compute the Required Expression:
$\text{Value} = a + 10b + 100c + 1000d$ $\text{Value} = 0 + 10(1) + 100(1) + 1000(0) = 10 + 100 = 110.$

Final answer

110

Common trap

Assuming the range search takes O(m log n) time by searching for each element individually from the root instead of continuing via tree traversal.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2014 Computer Science and Information Technology (CS) Session 3
Question: 49 of 65, printed as CS Q.39
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source