GATE CS 2020 Q41 — Binary Search Trees

To find and report all elements in the range $[a, b]$ within a balanced Binary Search Tree (BST) containing $n$ elements, we can use a standard range-search algorithm:

1. Locate the boundaries: We search for the keys $a$ and $b$ in the BST. Since the tree is balanced, searching for any key takes $\Theta(\log n)$ time. This identifies the split node where the paths to $a$ and $b$ diverge.
2. Traverse the range: From the split node, we traverse down towards $a$ and $b$. For any node $x$ visited:
   • If $x$ is within the range $[a, b]$, we report $x$ and recursively explore its subtrees.
   • If a subtree lies entirely within the range $[a, b]$, we can report all its elements using a standard in-order traversal. The time taken to traverse a subtree containing $m$ elements is $\Theta(m)$.

Complexity Analysis:

• The search paths from the root to $a$ and $b$ have a maximum depth of $O(\log n)$. Thus, the number of nodes visited on these boundary paths is $O(\log n)$.
• All other visited nodes belong to subtrees that lie entirely within the range $[a, b]$. The time spent traversing these subtrees is directly proportional to the number of elements reported, which is $\Theta(k)$.

Combining these two parts, the total worst-case time complexity is: