Consider this pattern: # let rec enumerate_from (t:'a color_tree) counter = match t with | Leaf x -> (Leaf counter, counter+1) | Branch (left,col,right) -> let (left',counter') = ... in let (right',counter'') = ... in ... ;;