module Main where

data Bst a = Nil | Node {
	elt :: a,
	l :: Bst a,
	r :: Bst a} deriving Show

insert_ntr Nil x = Node x Nil Nil
insert_ntr n x | x < elt n = n {l = insert_ntr (l n) x}
insert_ntr n x | x > elt n = n {r = insert_ntr (r n) x}
insert_ntr n x | otherwise = n

insert n x = recur n x id where
	recur Nil x fun = fun $ Node x Nil Nil
	recur n x fun | x < elt n = recur (l n) x $ fun . (\k -> n {l = k})
	recur n x fun | x > elt n = recur (r n) x $ fun . (\k -> n {r = k})
	recur n x fun | otherwise = n

mkTree f = foldl f Nil

main = do
	let l = [5,8,4,2,1,9,6,7,3,5]
	putStrLn . show . mkTree insert_ntr $ l
	putStrLn . show . mkTree insert $ l