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.


  [ this ]                  is nil         (   --> [ )
 
  [ ' [ 1
        [ 2
          [ 4
            [ 7 nil nil ]
            nil ]
          [ 5 nil nil ] ]
        [ 3
          [ 6
            [ 8 nil nil ]
            [ 9 nil nil ] ]
          nil ] ] ]         is tree        (   --> [ )
 
  [ dup nil = iff drop done
    unpack swap rot
    echo sp
    recurse
    recurse ]               is pre-order   ( [ -->   )
 
  [ dup nil = iff drop done
    unpack unrot
    recurse
    echo sp
    recurse ]               is in-order    ( [ -->   )
 
  [ dup nil = iff drop done
    unpack swap
    recurse
    recurse
    echo sp ]               is post-order  ( [ -->   )
 
  [ queue swap push
    [ dup empty? 
        iff drop done
      pop
      dup nil = iff 
        drop again
      unpack
      rot echo sp 
      dip push push 
      again ] ]             is level-order ( [ -->   )
 
  tree pre-order   cr
  tree in-order    cr
  tree post-order  cr
  tree level-order cr