Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Functional programming, design and analysis of algorithms / 4 / f / 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(\mathrm{Empty})=0,d(\mathrm{Node}lxr)=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.