```
(* Déterminer si une liste d'entiers correspond ou non aux profondeurs
des feuilles d'un arbre binaire, considérées dans l'ordre infixe.

Ainsi, la liste [1;3;3;2] correspond à un arbre
mais pas la liste [1;3;3]. *)

let rec is_tree_rec left right = match left, right with
| _, [] -> false
| [], [d] -> d = 0
| [], d :: l -> is_tree_rec [d] l
| d1 :: l1, d2 :: l2 when d1 = d2 -> is_tree_rec l1 (d1 - 1 :: l2)
| l1, d2 :: l2 -> is_tree_rec (d2 :: l1) l2

let is_tree l =
is_tree_rec [] l

(* tests *)

let () = assert (is_tree [0])
let () = assert (not (is_tree [1]))
let () = assert (is_tree [1;3;3;2])
let () = assert (not (is_tree [1;3;3]))
let () = assert (not (is_tree [1;3;2]))

(* Note : Il est facile d'adapter ce programme pour reconstruire l'arbre *)

type tree =
| E
| N of tree * tree

exception NoTree

let rec is_tree_rec left right = match left, right with
| _, [] -> raise NoTree
| [], [0, t] -> t
| [], [_] -> raise NoTree
| [], dt :: l -> is_tree_rec [dt] l
| (d1, t1) :: l1, (d2, t2) :: l2 when d1 = d2 ->
is_tree_rec l1 ((d1 - 1, N (t1, t2)) :: l2)
| l1, dt2 :: l2 -> is_tree_rec (dt2 :: l1) l2

let is_tree l =
is_tree_rec [] (List.map (fun i -> i, E) l)

```

This document was generated using caml2html