open List

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

type 'a init_last = 'a list * 'a list

let to_list (xs : 'a init_last) : 'a list =
  let (init, last) = xs in init @ rev last

let push_top (a : 'a) (xs : 'a init_last) : 'a init_last =
  let (init, last) = xs in (a :: init, last)

let push_end (xs : 'a init_last) (a : 'a) : 'a init_last =
  let (init, last) = xs in (init, a :: last)

let empty : 'a init_last = ([], [])

let walk t =
    let rec pom_walk t acc end_root =
    (* it's symmetric, so it could be start_root and the result would be correct too *)
        match t with
        | Null -> acc
        | Node (nr, l, r) ->
            if end_root then
                push_top nr (pom_walk r (pom_walk l acc false) false)
            else
                push_end (pom_walk r (pom_walk l acc true) true) nr
     in
        to_list (pom_walk t empty true)


(* EXAMPLE *)

let node a l r = Node (a, l, r)
let leaf a = node a Null Null

let example = walk (node 1 (node 2 (node 3 (leaf 4) (leaf 5)) Null) (leaf 6))