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