(* ---------- ex19 ---------- *)

type 'a tree = Nil | Node of 'a * 'a tree * 'a tree ;;

let rec howMany x tree =
	match tree with
		| Nil -> 0
		| Node(e,l,r) -> (if (x = e) then 1 else 0) + (howMany x l) + (howMany x r)
;;

howMany 3 (Node(1, Node(2, Nil, Nil) , Node(3, Nil, Nil))) ;;
howMany 4 (Node(1, Node(2, Nil, Nil) , Node(3, Nil, Nil))) ;;

let rec eqPairs tree = 
	match tree with
		| Nil -> 0
		| Node ((x,y),l,r) -> (if (x=y) then 1 else 0) + eqPairs l + eqPairs r 
;;

eqPairs (Node((1,1), Node((2,1), Nil, Nil) , Node((3,0), Nil, Nil))) ;;
eqPairs (Node((1,1), Node((2,2), Nil, Nil) , Node((2,2), Nil, Nil))) ;;

let rec treeToList tree =
	match tree with
		| Nil -> []
		| Node (e,l,r) -> e :: treeToList l @ treeToList r
;;

treeToList (Node(1, Node(2, Nil, Nil) , Node(3, Nil, Nil))) ;;
treeToList (Node((1,1), Node((2,2), Nil, Nil) , Node((2,2), Nil, Nil))) ;;

(* ---------- ex20 ---------- *)

let rec height tree =
	match tree with
		| Nil -> 0
		| Node(_,l,r) -> 1 + max (height r) (height l)
;;

height (Node(1, Nil, Nil)) ;;
height (Node(1, Node(2, Nil, Nil) , Nil)) ;;
height (Node(1, Node(2, Nil, Nil) , Node(3, Nil, Node(4, Nil, Nil)))) ;;


let balanced tree =
	match tree with
		| Nil -> true
		| Node(_,l,r) -> if abs (height l - height r > 1) then false else balanced l && balanced r
;;

balanced Nil ;;
balanced (Node(3,Node(5,Nil,Nil),Node(6,Nil,Nil))) ;;
balanced (Node(1,Nil,Node(2,Nil,Node(3,Nil,Nil)))) ;;

(* ---------- ex21 ---------- *)

let rec belongs n l =
	match l with
		| [] -> false
		| el::xl -> if (el = n) then true else belongs n xl
;;

let rec union l1 l2 =
	match l1 with
		| [] -> l2
		| el::xl1 -> if (belongs el l2) then union xl1 l2 else el::union xl1 l2
;;

let rec subtrees tree =
	match tree with
		| Nil -> [Nil]
		| Node(e,l,r) -> Node(e,l,r) :: union (subtrees l) (subtrees r) 
;;

subtrees Nil ;;
subtrees (Node(5,Nil,Node(6,Nil,Nil))) ;;

(* ---------- ex22 ---------- *)

let rec spring x tree =
	match tree with
		| Nil -> Node (x, Nil, Nil)
		| Node (e,l,r) -> Node (e, spring x l, spring x r)
;;

spring 9 Nil ;;
spring 9 (Node(5,Nil,Node(6,Nil,Nil))) ;;

(* ---------- ex23 ---------- *)

let rec fall tree =
	match tree with
		| Nil -> Nil
		| Node (_,Nil,Nil) -> Nil
		| Node (e,l,r) -> Node (e, fall l, fall r)
;;

fall Nil ;;
fall (Node(5,Nil,Node(6,Nil,Nil))) ;;
fall (Node(1,Node(2,Node(4, Nil, Nil),Node(5, Nil, Nil)),Node(3,Node(6, Nil, Nil),Nil))) ;;

(* ---------- ex24 ---------- *)

type 'a ntree = NNil | NNode of 'a * 'a ntree list

let rec treeToListNaux l =
	match l with
		| [] -> []
		| NNil::xl -> treeToListNaux xl
		| NNode (el,v)::xl -> el :: treeToListNaux v @ treeToListNaux xl
;;

let treeToListN tree = treeToListNaux [tree] ;;

treeToListN (NNode(1, [NNode(2,[NNil]); NNode(3,[NNil]); NNode(4,[NNode(5,[NNil])])])) ;;
treeToListN (NNode(1, [NNode(2,[NNode(3,[NNil]); NNode(4,[NNil])])])) ;;

let rec springl v l =
match l with
  | [] -> []
  | NNil::xs -> NNode(v,[]) :: springl v xs
  | NNode(x,[])::xs -> NNode(v,[NNode(v,[])]) :: springl v xs
  | NNode(x,c)::xs -> NNode (x, springl v c) :: springl v xs
;;

let spring v t = List.hd (springl v [t]) ;;

spring 9 (NNode(1, [NNode(2,[NNil]); NNode(3,[NNil])])) ;;
spring 9 (NNode(1, [NNode(2,[NNil; NNode(3,[]); NNil; NNode(4,[])])])) ;;

(* ---------- ex25 ---------- *)