// Binary search tree in F#, purely functional style

open System;

type 'a bst when 'a:comparison = 
  Nil | Node of ('a*'a bst*'a bst);;

let rec insert(x,t) =  
   match t with
     | Nil -> Node(x,Nil,Nil)
     | Node(y,left,right) when x<y -> Node(y,insert(x,left),right)
     | Node(y,left,right) when x>y -> Node(y,left,insert(x,right))
     | _ -> t;;

let rec search x t = 
   match t with
     | Node(y,_,_) when x=y -> true
     | Node(y,left,_) when x<y -> search x left
     | Node(y,_,right) -> search x right
     | _ -> false;;

// in-order traversal
let rec tostring t = 
   match t with
     | Nil -> ""
     | Node(x,left,right) -> 
          tostring(left) + " " + string(x) + tostring(right);;

let LLRotate = function
  | Node(x,Node(y,ll,lr),r) -> Node(y,ll,Node(x,lr,r))
  | t -> t;;

let mutable t = Nil;

for x in [6;2;9;7;8;1;4] do   // "imperitive" programming
   t <- insert(x,t)

Console.WriteLine(tostring(t));;