(* Maps a binary tree such that each nodes contains height info *)

type 'a tree =
    | Node of 'a tree * 'a * 'a tree
    | Nil

let rec map_with_height = function
    | Nil -> Nil
    | Node(l, x, r) ->
        let height = function
            | Nil -> 0
            | Node(l, (x, h), r) -> h

        let l' = map_with_height l
        let r' = map_with_height r
        let h = 1 + max (height l') (height r')
        Node(l', (x, h), r')