Task

Implement a binary tree where each node carries an integer,   and implement:

   pre-order,
   in-order, 
   post-order,     and 
   level-order   traversal. 


Use those traversals to output the following tree:

         1
        / \
       /   \
      /     \
     2       3
    / \     /
   4   5   6
  /       / \
 7       8   9

The correct output should look like this:

preorder:    1 2 4 7 5 3 6 8 9
inorder:     7 4 2 5 1 8 6 9 3
postorder:   7 4 5 2 8 9 6 3 1
level-order: 1 2 3 4 5 6 7 8 9



See also

   Wikipedia article:   Tree traversal.


data Tree = Empty | Node( value, left, right )
 
def
  preorder( Empty )          =  []
  preorder( Node(v, l, r) )  =  [v] + preorder( l ) + preorder( r )
 
  inorder( Empty )           =  []
  inorder( Node(v, l, r) )   =  inorder( l ) + [v] + inorder( r )
 
  postorder( Empty )         =  []
  postorder( Node(v, l, r) ) =  postorder( l ) + postorder( r ) + [v]
 
  levelorder( x ) =
    def
      order( [] )                 =  []
      order( Empty         : xs ) =  order( xs )
      order( Node(v, l, r) : xs ) =  v : order( xs + [l, r] )
 
    order( [x] )
 
tree =    Node( 1,
            Node( 2,
              Node( 4,
                Node( 7, Empty, Empty ),
                Empty ),
              Node( 5, Empty, Empty ) ),
            Node( 3,
              Node( 6,
                Node( 8, Empty, Empty ),
                Node( 9, Empty, Empty ) ),
              Empty ) )
 
println( preorder(tree) )
println( inorder(tree) )
println( postorder(tree) )
println( levelorder(tree) )