 Solution

ID: 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/e/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

∣ Empty ∣ = 0, ∣ Node l x r ∣ = 1 + ∣ l ∣ + ∣ r ∣

. The tree fold visits every node once, so this takes

Θ (n)

n

nodes.

 New to topics? Read the docs here!