lab8pp

let rec ltake = function
    | (0, _) -> []
    | (_,LNil) -> []
    | (n,LCons(x,xf)) -> x::ltake(n-1, xf())

let rec (@$) ll1 ll2 =
    match ll1 with
    | LNil -> ll2
    | LCons(x,xf) -> LCons(x,function() -> (xf()) @$ ll2);;

type llist = LNil | LCons of int * (unit -> llist);;

module Tree  =
struct
 	type 'a t = Tip | Node of 'a * 'a t * 'a t

let create = Tip;;

let rec insert tree (value) =
 	match tree with
 		| Tip -> Node(value, Tip, Tip)
 		| Node(info,t1,t2) ->
 			if(value<=info) then Node(info,insert t1(value),t2)
			else Node(info,t1,insert t2(value)
 	)
;;

let rec find tree (key) =
 	match tree with
 		| Node(value,t1,t2) ->
			if(key = value) then true
			else (if key<value then find t1 (key) else find t2 (key))
 		| Tip -> false
 ;;

let rec getPreOrder tree =
	match tree with
		| Tip -> []
		|	Node(value,t1,t2) -> value::getPreOrder t1@getPreOrder t2
;;

let rec getPostOrder tree =
	match tree with
		| Tip -> []
		|	Node(value,t1,t2) -> List.rev(value::List.rev(getPostOrder t1@getPostOrder t2))
;;

let rec getInOrder tree =
	match tree with
		| Tip -> []
		|	Node(value,t1,t2) -> getInOrder t1@(value::getInOrder t2)
;;

let rec getPreOrderL tree =
	match tree with
		| Tip -> LNil
		|	Node(value,t1,t2) -> LCons(value, function() -> getPreOrderL t1@$getPreOrderL t2)
;;

let rec getPostOrderL tree =
	match tree with
		| Tip -> LNil
		|	Node(value,t1,t2) -> List.rev(value::List.rev(getPostOrder t1@getPostOrder t2))
;;

let rec deletemin tree =
 match tree with
 	Node(value,Tip,t2) -> (value,t2)
 	| Node(value,t1,t2) ->
 		let (value,l) = deletemin t1
 		in (value,Node(value,l,t2))
 	| Tip -> failwith "error"
;;

let rec delete tree key =
 	match tree with
 		Tip -> Tip
		| Node(value,t1,t2) ->
 				if(key > value) then  Node(value, delete t1 key, t2)
 				else if(key = value) then
 					( match (t1, t2) with
						(Tip, t2) -> t2
 						| (t1, Tip) -> t1
						| _ -> let (value,t_right) = deletemin t2 in Node(value,t1,t_right)
 					)
 				else Node(value, t1, delete t2 key)
 ;;


 end;;

let s1 = let open Tree in create;;
let s2 = Tree.insert s1 (5)
let s3 = Tree.insert s2 (3)
let s4 = Tree.insert s3 (1)
let s5 = Tree.insert s4 (4)
let s6 = Tree.insert s5 (7)

ltake(10,Tree.getPreOrderL s6)
Tree.getPostOrder s6
Tree.getInOrder s6
Tree.find s3 (3)
let s7 = Tree.delete s6 5
Tree.getPreOrder s7