module type TREE =
sig
 type 'a bst_t

 val create: unit -> 'a bst_t
 val push: 'a -> 'a bst_t -> 'a bst_t
 val find: 'a -> 'a bst_t -> bool
(* val remove: 'a -> 'a bst_t *)
val preorder: 'a bst_t -> 'a list
val inorder: 'a bst_t -> 'a list
end;;

module T : TREE =
struct
	type 'a bst_t =
  | Leaf
  | Node of 'a bst_t * 'a * 'a bst_t (* Node (left, key, right) *)
(* a node may also carry a data associated with the key.
   It is omitted here for neater demonstration *)

	let create () = Leaf

	let rec push x = function
  | Leaf -> Node (Leaf, x, Leaf) (* Leaf is a STOP *)
  | Node (left, k, right) ->
    if x < k then Node (push x left, k, right) (* if x is smaller, go left *)
    else Node (left, k, push x right) (* otherwise, go right *)

	let rec find x = function
  | Leaf -> false
  | Node (left, k, right) ->
    if x < k then find x left
    else if x = k then true
    else find x right

	let rec preorder = function
   | Leaf -> []
   | Node (l, v, r) -> v :: (preorder l @ preorder r)

	let rec inorder = function
    | Leaf -> []
    | Node (l, v, r) -> inorder l @ (v :: inorder r)
end;;

T.create()
T.push(5)
T.push(3)
T.push(1)
T.push(4)
T.push(7)

T.find(3)
T.preorder()
T.inorder()