(* 1. Binary trees *)

type tree =
  | E
  | N of tree * tree

let rec size (t: tree): int = match t with
  | E -> 0
  | N(t1, t2) -> 1 + size t1 + size t2

let rec height (t: tree): int = match t with
  | E -> 0
  | N(t1, t2) -> 1 + max (height t1) (height t2)

let rec height_balanced (t: tree): bool = match t with
  | E -> true
  | N(t1, t2) -> abs (height t1 - height t2) <= 1
                 && height_balanced t1
                 && height_balanced t2

exception Unbalanced
let height_balanced t =
  let rec height_if_balanced (t: tree): int = match t with
    (* return height if balanced, and exception otherwise *)
    | E -> 0
    | N(t1, t2) ->
      let h1 = height_if_balanced t1 in
      let h2 = height_if_balanced t2 in
      if abs (h1 - h2) <= 1 then
        1 + max h1 h2
      else
        raise Unbalanced
  in
  try
    height_if_balanced t; true
  with
    Unbalanced -> false

(* alternative syntax for the try/with construction using an exception pattern in match

  match height_if_balanced t with
    | _ -> true
    | exception Unbalanced -> false

*)

let t1 = N(E,E)
let t2 = N(t1,E)

let _ = assert (height_balanced t1)
let _ = assert (height_balanced t2)
let _ = assert (not (height_balanced (N(t2,E))))

(* Variants: 
   let rec height_balanced (t: tree): int (*height*) * bool (*balanced?*) = match t with

type 'a option =
  | None
  | Some of 'a

   let rec height_balanced (t: tree): int option =
   (* return None if unbalanced, and Some h if balanced of height h *)
*)

(* 2. Binary search trees *)
(* In our binary search trees, each node carries an integer, and these integers
   are ordered from left to right. *)
type bst =
  | E
  | N of bst * int * bst
(* invariant: in N(t1, x, t2), elements in t1 are <= x and elements in t2 are >= x *)

(* 
   Define the following functions on BST:

   mem: int -> bst -> bool 
   tests whether the integer appears in the tree
   time complexity: proportional to the height of the tree

   add: int -> bst -> bool
   adds an integer in the tree
   time complexity: proportional to the height of the tree

   check: bst -> bool
   checks whether a tree is a well-formed BST
   hint: define an auxiliary function 'check_aux: bst -> int -> int -> bool' 
   such that 'check_aux t a b' checks whether t is a binary search tree
   containing numbers in the interval [a, b]
*)

(* 3. Sequences *)
type 'a seq =
  | Elt of 'a
  | Seq of 'a seq * 'a seq
(* Seq(Elt 1, Seq(Elt 2, Elt 3)) and Seq(Seq(Elt 1, Elt 2), Elt 3)
   are two representations of the sequence [1; 2; 3] *)

(*
   Define the following functions on SEQ:

   mem: 'a -> 'a seq -> bool
   tests whether the element appears in the sequence

   seq_to_list: 'a seq -> 'a list
   builds a list with the same elements in the same order
   
   additional challenge: tail recursive version of seq_to_list
   Hint use an auxiliary function whick works with an accumulator and a list of sequences to explore
*)