Given a tree whose leaves are labeled by numbers, let us replace every label by the minimum label without traversing the tree twice.

type tree = Leaf of int | Branch of tree * tree;;

let repmin (t:tree) : tree =
  let present = ref max_int in
  let make = .!.<fun future -> .~(
    let rec process = function
      | Leaf x ->
          present := min x !present;
          .<Leaf future>.
      | Branch (t1,t2) ->
          .<Branch (.~(process t1), .~(process t2))>.
    in process t)>. in
  make !present;;

repmin (Branch (Branch (Leaf 1, Leaf 2), Leaf 3));;
(* Branch (Branch (Leaf 1, Leaf 1), Leaf 1) *)

Julia L. Lawall, 2001. Implementing circularity using partial evaluation. In Proceedings of PADO 2001: 2nd symposium on programs as data objects, ed. Olivier Danvy and Andrzej Filinski, 84–102. Lecture Notes in Computer Science 2053. (slides)