(* 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')