سوال ۶۸ کنکور ارشد علوم کامپیوتر ۱۳۹۹

The median of the $n$ keys stored in a binary search tree (BST) is the element whose rank is $\lfloor n/2 \rfloor$ in sorted order. An in-order traversal of a BST visits the keys in increasing order, so the median is simply the $\lfloor n/2 \rfloor$-th key produced by that traversal.

Counting to the middle element. A plain BST stores no rank or subtree-size information at its nodes. To reach the element of rank $\lfloor n/2 \rfloor$ we must perform an in-order walk and count nodes until we have emitted $\lfloor n/2 \rfloor$ of them. That stops after visiting about $n/2$ nodes:

$T(n) = \Theta\!\left(\frac{n}{2}\right) = \Theta(n).$

In Big-$O$ notation constant factors are discarded, so $O\!\left(\tfrac{n}{2}\right)$ and $O(n)$ denote the same growth class — option (1) is the canonical, simplified form.

Why not $O(\log n)$? The height of a balanced BST is $O(\log n)$, but a single root-to-leaf path does not locate the median: there is no way to know in advance which key has rank $n/2$ without counting. To select by rank in $O(\log n)$ you would need an order-statistic tree (each node augmented with the size of its subtree). The question speaks of an ordinary binary search tree, so that augmentation is not available and the in-order count dominates.

Hence the time order is linear, $O(n)$.

Official key (دو گزینه‌ای): this question is officially dual-keyed — both option (1) $O(n)$ and option (2) $O\!\left(\tfrac{n}{2}\right)$ are accepted, because $O\!\left(\tfrac{n}{2}\right)=O(n)$. The more defensible choice is option (1), since Big-$O$ drops constant factors and $O(n)$ is the standard simplified form.

Pitfall: Do not confuse the $O(\log n)$ height of a balanced BST with the cost of selecting by rank. Without subtree-size augmentation, finding the median (or any $k$-th order statistic) requires an in-order count and is $\Theta(n)$.