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.


 
main(args(2)) :=
    "preorder: " ++ toString(preOrder(testTree)) ++
    "\ninoder: " ++ toString(inOrder(testTree)) ++
    "\npostorder: " ++ toString(postOrder(testTree)) ++
    "\nlevel-order: " ++ toString(levelOrder(testTree));
 
Node ::= (value : int, left : Node, right : Node);
 
preOrder(n) := [n.value] ++
               (preOrder(n.left) when isDefined(n, left) else []) ++
               (preOrder(n.right) when isDefined(n, right) else []);
 
inOrder(n) :=  (inOrder(n.left) when isDefined(n, left) else []) ++
               [n.value] ++
               (inOrder(n.right) when isDefined(n, right) else []);
 
postOrder(n) := (postOrder(n.left) when isDefined(n, left) else []) ++
                (postOrder(n.right) when isDefined(n, right) else []) ++
                [n.value];
 
levelOrder(n) := levelOrderHelper([n]);
levelOrderHelper(ns(1)) :=
    let
        n := head(ns);
    in
        [] when size(ns) = 0 else
        [n.value] ++ levelOrderHelper(tail(ns) ++
        ([n.left] when isDefined(n, left) else []) ++
        ([n.right] when isDefined(n, right) else []));
 
testTree :=
    (value : 1,
     left : (value : 2,
             left : (value : 4,
                     left : (value : 7)),
                     right : (value : 5)),
             right : (value : 3,
                      left : (value : 6,
                              left : (value : 8),
                              right : (value : 9))
             )
    );
 