Defining a binary tree and traversing it

In this recipe, we will look at a data type that is recursively defined. We will define a binary tree and then explore functions to traverse it.

Getting ready

Create a new project binary-tree-traverse using the simple Stack template. Change into this directory:

    stack new binary-tree-traverse simple

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...