GATE CS 2014 Set 3 Q39 — Binary Search Trees

To find the sum of all elements in a balanced binary search tree (BST) $T$ of size $n$ that fall within the range $[L, H]$ (where there are $m$ such elements), we can perform a standard range search:

1. Search for the boundaries: We search for $L$ and $H$ in the BST. Since the tree is balanced, the height of the tree is $O(\log n)$. Finding the split node and traversing down to the boundaries takes $O(\log n)$ time.
2. Traverse and sum the elements: The elements lying strictly between the search paths of $L$ and $H$ belong to subtrees that are completely inside the range $[L, H]$. We can traverse these subtrees to sum their elements. Since there are exactly $m$ such elements, traversing them takes $O(m)$ time.

Thus, the tightest upper bound on the time complexity to compute the sum is:

We are given the upper bound in the form:

Comparing $O(\log n + m)$ with $O(n^a \log^b n + m^c \log^d n)$:

• For the first term $n^a \log^b n = \log n$, we get:
  $a = 0$ and $b = 1$
• For the second term $m^c \log^d n = m$, we get:
  $c = 1$ and $d = 0$

Now, we calculate the required value: