Counting 2-3 Trees

A 2-3 tree is a tree whose nodes have either two or three children, with the property that every two-child node is at an even depth, and every three-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

Note the keyword and, which we use to define mutually recursive ADTs.

Implement the function

val count : 'a tree23 -> int

so that count t is the number of nodes in t. Note that this function will need to be mutually recursive.

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