Solution
= Solution
An empty <binary search tree> has zero nodes; a nonempty node contributes one in addition to the sizes of its two subtrees:
``
size :: STree a -> Integer
size = foldSTree (\left _ right -> 1 + left + right) 0
``
The answer is $\boxed{|\operatorname{Empty}|=0,\quad|\operatorname{Node}\ l\ x\ r|=1+|l|+|r|}$. The <tree fold> visits every node once, so this takes $\Theta(n)$ arithmetic operations for $n$ nodes.