(* If you would like, write how many hours you spent on this homework:

  XXX

*)

(** Q1 **)

(*
    Q1.1: Explain why the invariant is maintained for each of the following
    functions, and UNREACHABLE should never be reached:
    - mk: TODO
    - cons: TODO
    - uncons: TODO
*)


(* Q1.2: 
    - map: TODO
    - filter: TODO
*)


(** Q2 **)

type 'a raw_tree = | Leaf of 'a | Node of 'a raw_tree * 'a raw_tree

module type BalancedTreeSig = sig
    (* The type for balanced trees. *)
    type 'a t

    (* Is the balanced tree well-formed? *)
    val well_formed : 'a t -> bool

    (* Build the balanced tree consisting of a single leaf. *)
    val leaf : 'a -> 'a t

    (* Build the balanced tree consisting of a node (or returning None if it would result in a non-balanced tree.) *)
    val node : 'a t -> 'a t -> 'a t option

    (* Return the underlying raw_tree. *)
    val to_tree : 'a t -> 'a raw_tree
end

module BalancedTree = struct
    type 'a t = unit (* TODO: Replace with your chosen type! *)

    let well_formed _ = failwith "TODO"

    let leaf _ = failwith "TODO"

    let node _ _ = failwith "TODO"

    let to_tree _ = failwith "TODO"
end