type arbre =  Noeud of bool ref  * (char * arbre) list ref

let vide () = Noeud(ref false,ref[])

let parcours a lc =
    let get_letter (letter, _) = letter
  in
    let rec find_letter arr letter = match arr, letter with
    | [], _ -> ('#', vide())
    | curr::tail, letter' -> if letter' = (get_letter curr) then curr else find_letter tail letter'
  in
    let rec traverse a lc : ('a * 'b * 'c) = match a, lc with
    | node, [] when node = vide() -> ([], [], a)
    | node, curr::tail when node = vide() -> (lc, [], a)
    | (Noeud(_, arr)) as node, curr::tail -> (
      let (fl, n) = find_letter !arr curr in
      if fl = curr then traverse n tail
      else if fl = '#' then ((curr@tail), [], node)
    )
  in traverse a lc