= Solution
Count each <data constructor> once, including each `Two`:
``
size :: Tree a -> Int
size (One _) = 1
size (Two l r) = 1 + size l + size r
``
<Structural induction> verifies the count: a leaf contributes one; an internal node contributes itself and the disjoint occurrences in its two <subtrees>. Fully evaluating the result takes <linear time> in the number of nodes. This <type signature> uses machine `Int` as usual in the examination; `Integer` avoids overflow for arbitrarily large inputs.
Back to article page
