Summing 3-2 Trees

A 3-2 tree is a tree whose nodes have either two or three children, with the property that every three-child node is at an even depth, and every two-child node is at an odd depth.

type 'a tree23 =
  | Empty2
  | Node2 of 'a * 'a tree32 * 'a tree32
and 'a tree32 =
  | Empty3
  | Node3 of 'a * 'a tree23 * 'a tree23 * 'a tree23

Implement the function

val sum : int tree32 -> int

so that sum t is the sum of all the values in t. Note that this function will need to be mutually recursive.

Examples

let example : int tree23 =
  Node3
    ( 1
    , Node2
        ( 2
        , Node3 (3, Empty2, Empty2, Empty2)
        , Empty3
        )
    , Node2
        ( 6
        , Node3 (7, Empty2, Empty2, Empty2)
        , Node3 (4, Empty2, Empty2, Empty2)
        )
    , Empty2
    )
let _ = assert (sum example = 1 + 2 + 3 + 6 + 7 + 4)
let _ = assert (sum Empty3 = 0)