1 files changed, 87 insertions, 0 deletions
diff --git a/Haskell-book/11/BinaryTree.hs b/Haskell-book/11/BinaryTree.hs
new file mode 100644
index 0000000..854deee
--- /dev/null
+++ b/Haskell-book/11/BinaryTree.hs
@@ -0,0 +1,87 @@
+module BinaryTree where
+
+data BinaryTree a = Leaf
+                  | Node (BinaryTree a) a (BinaryTree a)
+                  deriving (Eq, Ord, Show)
+
+insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
+insert' b Leaf = Node Leaf b Leaf
+insert' b (Node left a right)
+  | b == a = Node left a right
+  | b < a = Node (insert' b left) a right
+  | b > a = Node left a (insert' b right)
+
+mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
+mapTree _ Leaf = Leaf
+mapTree f (Node left v right) =
+    Node (mapTree f left) (f v) (mapTree f right)
+
+preorder :: BinaryTree a -> [a]
+preorder Leaf = []
+preorder (Node left v right) =
+    v : ((preorder left) ++ (preorder right))
+
+inorder :: BinaryTree a -> [a]
+inorder Leaf = []
+inorder (Node left v right) =
+    (inorder left) ++ [v] ++ (inorder right)
+
+postorder :: BinaryTree a -> [a]
+postorder Leaf = []
+postorder (Node left v right) =
+    ((postorder left) ++ (postorder right)) ++ [v]
+
+foldTree :: (a -> b -> b)
+         -> b
+         -> BinaryTree a
+         -> b
+foldTree _ acc Leaf = acc
+foldTree f acc (Node left v right) = foldTree f r left
+    where r = foldTree f (f v acc) right
+
+testTree :: BinaryTree Integer
+testTree =
+    Node (Node Leaf 1 Leaf)
+         2
+         (Node Leaf 3 Leaf)
+
+testPreorder :: IO ()
+testPreorder =
+    if preorder testTree == [2, 1, 3]
+    then putStrLn "Preorder fine!"
+    else putStrLn "Bad news bears."
+
+testInorder :: IO ()
+testInorder =
+    if inorder testTree == [1, 2, 3]
+    then putStrLn "Inorder fine!"
+    else putStrLn "Bad news bears."
+
+testPostorder :: IO ()
+testPostorder =
+    if postorder testTree == [1, 3, 2]
+    then putStrLn "Postorder fine!"
+    else putStrLn "postorder failed check"
+
+main :: IO ()
+main = do
+    testPreorder
+    testInorder
+    testPostorder
+
+testTree' :: BinaryTree Integer
+testTree' =
+    Node (Node Leaf 3 Leaf)
+         1
+         (Node Leaf 4 Leaf)
+
+mapExpected =
+    Node (Node Leaf 4 Leaf)
+         2
+         (Node Leaf 5 Leaf)
+
+-- acceptance test for mapTree
+mapOkay =
+    if mapTree (+1) testTree' == mapExpected
+       then print "yup okay!"
+       else error "test failed!"