type 'a llist = LEmpty | LCons of 'a * (unit -> 'a llist);;

module BST : 
sig
(*type 'a llist*)
val create: unit -> unit
val push: 'a -> unit
val remove: int -> unit
val find: int -> bool
val getBFS: unit -> int llist
val getDFS: unit -> int llist
val llistToNormal: int llist -> int list
end=
struct
(*type 'a llist = LEmpty | LCons of 'a * (unit -> 'a llist)*)
type 'a nnode = Empty | Node of 'a * 'a nnode * 'a nnode
let root = ref Empty

(* If root isn't empty, function clears it *)
let create() = root := Empty

(* Add item to tree *)
let push(elem) = 
let rec add = function
| Node(v, l, r) -> if elem > v then
Node(v, l, add r)
else 
Node(v, add l, r)
| Empty -> Node(elem, Empty, Empty)
in root := add(!root)

(* Search for successor of specified node and remove it*)
let rec findSuccessor = function
| Node(v, l, r) -> 
if l = Empty then (v, r)
else
let (value, result) = findSuccessor(l) in
(value, Node(v, result, r))
| Empty -> Null, Empty

(* Remove specified item from the tree *)
let remove(elem) = 
let rec removeNode = function
| Node(v, l, r) -> 
if v = elem then 
let (value, result) = findSuccessor(r) in
if result = Empty then
l
else 
Node(value, l, result)
else 
if elem < v then
Node(v, removeNode l, r)
else
Node(v, l, removeNode r)
| Empty -> Empty
in root := removeNode(!root)

(* Find element in the tree *)
let find(elem) = 
let rec find = function
| Node(v, l, r) -> 
if v = elem then true 
else
if elem < v then find(l)
else find(r) 
| Empty -> false
in find(!root) 

(* Create lazy list out of tree nodes using DFS preorder algorithm*)
let getDFS() = 
let rec depth = function
| [] -> LEmpty
| Empty::t -> depth(t)
| Node(v, l, r)::t -> LCons(v, fun() -> depth( [l; r] @ t))
in depth [!root]

(* Create lazy list out of tree nodes using BFS algorithm*)
let getBFS()= 
let rec breadth = function
| [] -> LEmpty
| Empty::t -> breadth(t)
| Node(v, l, r)::t -> LCons(v, fun() -> breadth( t @ [l; r] ))
in breadth [!root]

(* Transform lazy list to normal *)
let rec llistToNormal = function
| LCons(v, f) -> v::llistToNormal(f())
| LEmpty -> []
end;;

BST.create();;
BST.push(5);;
BST.push(4);;
BST.push(3);;
BST.push(2);;
BST.push(1);;

BST.remove(3);;

BST.llistToNormal(BST.getBFS());;

BST.create();;
BST.push(5);;
BST.push(3);;
BST.push(4);;
BST.push(1);;
BST.push(8);;
BST.push(9);;
BST.push(7);;

BST.llistToNormal(BST.getBFS());;
BST.llistToNormal(BST.getDFS());;