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.


bintree = cluster [T: type] is leaf, node,
                               pre_order, post_order, in_order, level_order
    branch = struct[left, right: bintree[T], val: T]
    rep = oneof[br: branch, leaf: null]
 
    leaf = proc () returns (cvt)
        return(rep$make_leaf(nil))
    end leaf
 
    node = proc (val: T, l,r: cvt) returns (cvt)
        return(rep$make_br(branch${left:up(l), right:up(r), val:val}))
    end node
 
    pre_order = iter (n: cvt) yields (T)
        tagcase n
            tag br (b: branch):
                yield(b.val)
                for v: T in pre_order(b.left) do yield(v) end
                for v: T in pre_order(b.right) do yield(v) end
            tag leaf:
        end
    end pre_order
 
    in_order = iter (n: cvt) yields (T)
        tagcase n
            tag br (b: branch):
                for v: T in in_order(b.left) do yield(v) end
                yield(b.val)
                for v: T in in_order(b.right) do yield(v) end
            tag leaf:
        end
    end in_order     
 
    post_order = iter (n: cvt) yields (T)
        tagcase n
            tag br (b: branch):
                for v: T in post_order(b.left) do yield(v) end
                for v: T in post_order(b.right) do yield(v) end
                yield(b.val) 
            tag leaf:
        end
    end post_order 
 
    level_order = iter (n: cvt) yields (T)
        bfs: array[rep] := array[rep]$[n]
        while ~array[rep]$empty(bfs) do
            cur: rep := array[rep]$reml(bfs)
            tagcase cur
                tag br (b: branch):
                    yield(b.val)
                    array[rep]$addh(bfs,down(b.left))
                    array[rep]$addh(bfs,down(b.right))
                tag leaf:
            end
        end
    end level_order
end bintree
 
start_up = proc ()
    bt = bintree[int]
 
    po: stream := stream$primary_output()
    tree: bt := bt$node(1,
                    bt$node(2,
                        bt$node(4,
                            bt$node(7, bt$leaf(), bt$leaf()),
                            bt$leaf()),
                        bt$node(5, bt$leaf(), bt$leaf())),
                    bt$node(3,
                        bt$node(6,
                            bt$node(8, bt$leaf(), bt$leaf()),
                            bt$node(9, bt$leaf(), bt$leaf())),
                        bt$leaf()))
 
    stream$puts(po, "preorder:   ")
    for i: int in bt$pre_order(tree) do 
        stream$puts(po, " " || int$unparse(i)) 
    end
 
    stream$puts(po, "\ninorder:    ")
    for i: int in bt$in_order(tree) do 
        stream$puts(po, " " || int$unparse(i)) 
    end
 
    stream$puts(po, "\npostorder:  ")
    for i: int in bt$post_order(tree) do 
        stream$puts(po, " " || int$unparse(i)) 
    end
 
    stream$puts(po, "\nlevel-order:")
    for i: int in bt$level_order(tree) do 
        stream$puts(po, " " || int$unparse(i)) 
    end
end start_up