Haskell Cookbook

How to do it...

1. Open src/Main.hs; we will be using this file for our recipe.
2. Define a binary tree data type:

        data BinaryTree a = Leaf          | BinaryTree { left :: BinaryTree a                               , val :: a                               , right :: BinaryTree a }          deriving Show

3. Write the helper functions empty, singleton, and node to create an empty tree and a tree with a single node, and compose the two trees with a value to create a new tree:

        empty :: BinaryTree a        empty = Leaf       singleton :: a -> BinaryTree a       singleton x = BinaryTree Leaf x Leaf       node :: BinaryTree a -> a -> BinaryTree a -> BinaryTree a       node l x r = BinaryTree { left = l, val = x, right = r }

4. Define in-order depth first traversal for the binary tree:

        dfTraverse :: BinaryTree a -> [a]        dfTraverse Leaf = [] dfTraverse tree ...