# Untitled

By: a guest on Aug 1st, 2012  |  syntax: None  |  size: 1.67 KB  |  hits: 7  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
2.
3. > import Data.Maybe
5. > data BinTree a = Empty | Branch {left :: BinTree a ,  val :: a, right:: BinTree a} deriving Show
6.
7. > isBST :: BinTree a -> Bool
8. > isBST Empty = True
9. > isBST (Branch Empty b Empty) = True
10. > isBST (Branch a b Empty) = if (fromJust (largest a) > b) then False else isBST a
11. > isBST (Branch Empty b c) = if (b > fromJust (smallest c)) then False else isBST c
12. > isBST (Branch a b c) = if isBST (Branch a b Empty) && isBST (Branch Empty b c) then True else False
13.
14. > largest :: Ord a => BinTree a -> Maybe a
15. > largest Empty = Nothing
16. > largest (Branch Empty b Empty) = Just b
17. > largest (Branch a b Empty) = if largest a < b then Just b else Just (largest a)
18. > largest (Branch Empty b c) = if largest c < b then Just b else Just (largest c)
19. > largest (Branch a b c) = if largest c > largest a then Just largest (Branch Empty b (Branch Empty (largest c) Empty)) else Just largest (Branch (Branch Empty (largest a) Empty) b Empty)
20.
21. > smallest :: Ord a => BinTree a -> Maybe a
22. > smallest Empty = Nothing
23. > smallest (Branch Empty b Empty) = Just b
24. > smallest (Branch a b Empty) = if smallest a > b then Just b else Just (smallest a)
25. > smallest (Branch Empty b c) = if smallest c > b then Just b else Just (smallest c)
26. > smallest (Branch a b c) = if smallest c < smallest a then Just smallest (Branch Empty b (Branch Empty (smallest c) Empty)) else Just smallest (Branch (Branch Empty (smallest a) Empty) b Empty)
27.
28.  addBST :: BinTree a -> BinTree a -> a -> BinTree a
29.
30.  removeLargestBST :: BinTree a -> (a, BinTree a)
31.  removeLargestBST Empty = ((), Empty)
32.
33.  removeLargestBST
34.
35.
36.  removeSmallestBST :: BinTree a -> (a, BinTree a)