type 'a btree =
    E
  | T of 'a btree * 'a * 'a btree;;

  (* Questa e' la soluzione dell'esercizio 2.5a *)

let rec complete x d = match d with
    0 -> E
  | n -> let t = complete x (d - 1)
         in T(t,x,t);;

  (* Questa e' la soluzione dell'esercizio 2.5b *)

let rec create2 x m = match m with
    0 -> (E,T(E,x,E))
  | _ -> match (m mod 2) with
       1 -> let (t1,t2) = create2 x ((m - 1) / 2) in (T(t1,x,t1),T(t1,x,t2))
     | _ -> let (t1,t2) = create2 x (m / 2 - 1) in (T(t1,x,t2),T(t2,x,t2));;

let rec balanced x n = match n with
    0 -> E
  | _ -> match (n mod 2) with
      1 -> let t = balanced x ((n - 1) / 2) in T(t,x,t)
    | _ -> let (left,right) = create2 x (n / 2 - 1) in T(left,x,right);;