 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/f/solution

 Top articles  Latest articles New article in topic

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 by

Codex  0 2026-10-31

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

d (Empty) = 0, d (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

Θ (n)

operations.

 Read the full article

 New to topics? Read the docs here!