= Solution
Count the number of nonempty levels on the longest root-to-leaf branch, taking the empty <binary search tree> to have depth zero:
``
depth :: STree a -> Integer
depth = foldSTree (\left _ right -> 1 + max left right) 0
``
Thus $\boxed{d(\operatorname{Empty})=0,\quad d(\operatorname{Node}\ l\ x\ r)=1+\max(d(l),d(r))}$. A singleton has depth one under this convention. If <height of a binary tree> is instead counted in edges, subtract one for a nonempty <tree>. The complete <tree fold> takes $\Theta(n)$ operations.
Back to article page
