type 'a planar_tree = Node of 'a * 'a planar_tree list
type 'a tree = Empty | Bin of 'a * 'a tree * 'a tree

type direction = Up | Down
type dyckword = direction list

let rec aux_dyck l acc = match l with
    [] -> acc
  | h::t -> match h with
              Empty -> aux_dyck t acc
            | Bin(n, l, r) -> match l,r with
                                Empty, Empty -> aux_dyck t (Down::acc)
                              | _,_ -> aux_dyck (l::r::t) (Up::acc)

let full_to_dyck t = match t with
    Empty -> []
  | Bin(n, l, r) -> match l,r with
                      Empty, Empty -> []
                    | _,_ -> let res = aux_dyck (l::r::[]) [Up] in
                             match res with
                               [] -> []
                             | h::t -> List.rev t


let rec dyck_to_full l = match l with
  | Up::Down::t -> Bin(1, Bin(1, Empty, Empty), dyck_to_full t)
  | Down::t -> Bin(1, Empty, Empty)
  | Up::Up::t -> Bin(1, dyck_to_full (Up::t), dyck_to_full t)
  | Up::[] | [] -> Bin(1, Empty, Empty)


let t = Bin(1, Bin(2, Bin(4, Bin(9, Empty, Empty), Bin(9, Empty, Empty)), Bin(6, Empty, Empty)), Bin(3, Bin(7, Bin(10, Empty, Empty), Bin(10, Empty, Empty)), Bin(7, Empty, Empty)))

           dyck_to_full (full_to_dyck t);;