Defining a binary tree data type

In a binary tree, each node has at most two children. We will define a data structure to encompass the left and right subtrees of each node.

Getting ready

The code in the recipe will represent the following tree. The root node is labeled n3 with a value of 3. It has a left node n1 of value 1, and a right node n2 of value 2.

How to do it...

1. This code requires no imports. We can jump in and define the data structure recursively. A tree can either be a node with values or null/empty:

   data Tree a = Node { value	:: a
                      , left  :: (Tree a)
                      , right:: (Tree a) }
               | Leaf 
               deriving Show

2. In main, create the tree shown in the preceding diagram and print it out:

   main = do
     let n1 = Node { value = 1, left = Leaf, right = Leaf }
     let n2 = Node { value = 2, left = Leaf, right = Leaf }
     let n3 = Node { value = 3, left = n1,   right = n2 }
     print n3

3. The full tree is printed out as follows:

   $ runhaskell Main.hs
   
   Node {...