data Tree a = EMPTY | NODE (Tree a, a, Tree a) main :: IO () main = do putStrLn "A simple Binary Search Tree checker" putStrLn "The Result:" putStr "Valid BST: " putStrLn . show $ checkBST bst putStr "Invalid BST: " putStrLn . show $ checkBST nobst bst :: Tree Int bst = (NODE((NODE((NODE(EMPTY,1,EMPTY)),3,(NODE(EMPTY,5,EMPTY))),7,(NODE((NODE(EMPTY,8,EMPTY)),9,(NODE((NODE(EMPTY,11,EMPTY)),12,EMPTY))))))) nobst :: Tree Int nobst = (NODE((NODE(EMPTY,6,(NODE(EMPTY,12,EMPTY)))),8,EMPTY)) checkBST :: (Ord a) => Tree a -> Bool checkBST EMPTY = True checkBST (NODE (left,val,right)) = checkBSTBelow left val && checkBSTAbove right val checkBSTBelow :: (Ord a) => Tree a -> a -> Bool checkBSTBelow EMPTY _ = True checkBSTBelow (NODE (left,val,right)) upBound = val < upBound && checkBSTBelow left val && checkBSTBetween right val upBound checkBSTAbove :: (Ord a) => Tree a -> a -> Bool checkBSTAbove EMPTY _ = True checkBSTAbove (NODE (left,val,right)) lowBound = lowBound < val && checkBSTAbove right val && checkBSTBetween left lowBound val checkBSTBetween :: (Ord a) => Tree a -> a -> a -> Bool checkBSTBetween EMPTY _ _ = True checkBSTBetween (NODE (left,val,right)) lowBound upBound = lowBound < val && val < upBound && checkBSTBetween left lowBound val && checkBSTBetween right val upBound