I want to define a binary tree function sumOfOdd() that calculates the sum of nodes at odd levels, where the first node starts at 0. For example, the tree T = t(leaf, t(t(leaf, leaf), leaf)) would have the result sumOfOdd(T) = 4 because there are two nodes at level 1 and two at level 3.
I have started by making a function n(t) that calculates the number of nodes in the tree:
- n(leaf) = 1
- n(T(A,B)) = n(A) + n(B)
I am not sure how I should define the rescursive part of sumOfOdd() to only select the odd levels. My base case is:
- sumOfOdd(leaf) = 0
I was thinking of splitting the function into two steps (one branch for even and one for odd) like this:
- sumOfOdd(leaf) = 0
- sumOfOdd(T(T(A,B),T(C,D)) = ...
Any ideas?
A common strategy when defining recursive functions is to slightly generalise the problem. We instead define a function $evensAndOdds : Trees \to \mathbb{N} \times \mathbb{N}$, such that given a tree $t$, we have $evensAndOdds(t) = ($number of nodes at even depth, number of nodes at odd depth$)$.
For convenience, we define $flip((x, y)) = (y, x)$, and we define $(a, b) + (c, d) = (a + c, b + d)$. We then define $evensAndOdds$ recursively as follows:
Then we recursively define our function by $evensAndOdds(leaf) = (1, 0)$ and $evensAndOdds(t(a, b)) = (1, 0) + flip(evensAndOdds(a) + evensAndOdds(b))$.
We can then easily use $evensAndOdds$ to define $sumOfOdd$.