1. (* Maps a binary tree such that each nodes contains height info *)
  2.  
  3. type 'a tree =
  4.     | Node of 'a tree * 'a * 'a tree
  5.     | Nil
  6.  
  7. let rec map_with_height = function
  8.     | Nil -> Nil
  9.     | Node(l, x, r) ->
  10.         let height = function
  11.             | Nil -> 0
  12.             | Node(l, (x, h), r) -> h
  13.  
  14.         let l' = map_with_height l
  15.         let r' = map_with_height r
  16.         let h = 1 + max (height l') (height r')
  17.         Node(l', (x, h), r')