(* 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
(* match height_if_balanced t with *)
(* | _ -> true *)
(* | exception Unbalanced -> false *)
(* 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
*)