open Printf;;

type 'a tree=Nill | BST of 'a tree * 'a *  'a tree;;

let rec insert x bts =match bts with
| Nill -> BST (Nill,x,Nill)
| BST (left,n,right) -> if x>n then BST(left,n,insert x right)
                        else if x<n then BST(insert x left,n,right)
                        else BST(left,x ,right);;
let insert_from_list l=
    List.fold_left (fun bst x -> insert x bst) Nill l;;

let bst1=insert_from_list [7;3;9;1;4;];;

let rec inorder =function
| Nill -> printf "\n"
| BST(left,node,right) -> inorder left ; printf "%d " node; inorder right;;

inorder bst1;;

let print_level x bst=
  let rec print_level_aux x count bst = match bst with
        | Nill ->()
        | BST(l,n,r) -> if (count == x) then (printf "%d " n)
                        else print_level_aux x (count+1) l;print_level_aux x (count+1 ) r in
  print_level_aux x 0 bst;;

print_level 1 bst1;;

let rec h1 = function
| Nill->0
|BST(l,n,r) ->1+ max (h1 l) (h1 r);;


let print_levels bst=
  let rec print_levels_aux bst level h=
    if level < h then (printf "\n L %d :" level ;print_level level bst ; print_levels_aux bst (level+1) h)
    else () in
    print_levels_aux bst 0 (h1 bst);;

print_levels bst1;;

let list_from_level l bst =
  let rec func_aux lvl bst  l count = match bst with
  |Nill -> l
  | BST(left,x,right) -> if(lvl == count) then x::l
                        else  func_aux lvl left l (count+1) ;func_aux lvl right l (count+1) in
  func_aux l bst [] 0;;


  List.iter (fun x-> printf "%d" x) (list_from_level 2 bst1);;