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.


import std.stdio, std.traits;
 
const final class Node(T) {
    T data;
    Node left, right;
 
    this(in T data, in Node left=null, in Node right=null)
    const pure nothrow {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}
 
// 'static' templated opCall can't be used in Node
auto node(T)(in T data, in Node!T left=null, in Node!T right=null)
pure nothrow {
    return new const(Node!T)(data, left, right);
}
 
void show(T)(in T x) {
    write(x, " ");
}
 
enum Visit { pre, inv, post }
 
// 'visitor' can be any kind of callable or it uses a default visitor.
// TNode can be any kind of Node, with data, left and right fields,
// so this is more generic than a member function of Node.
void backtrackingOrder(Visit v, TNode, TyF=void*)
                      (in TNode node, TyF visitor=null) {
    alias trueVisitor = Select!(is(TyF == void*), show, visitor);
    if (node !is null) {
        static if (v == Visit.pre)
            trueVisitor(node.data);
        backtrackingOrder!v(node.left, visitor);
        static if (v == Visit.inv)
            trueVisitor(node.data);
        backtrackingOrder!v(node.right, visitor);
        static if (v == Visit.post)
            trueVisitor(node.data);
    }
}
 
void levelOrder(TNode, TyF=void*)
               (in TNode node, TyF visitor=null, const(TNode)[] more=[]) {
    alias trueVisitor = Select!(is(TyF == void*), show, visitor);
    if (node !is null) {
        more ~= [node.left, node.right];
        trueVisitor(node.data);
    }
    if (more.length)
        levelOrder(more[0], visitor, more[1 .. $]);
}
 
void main() {
    alias N = node;
    const tree = N(1,
                      N(2,
                           N(4,
                                N(7)),
                           N(5)),
                      N(3,
                           N(6,
                                N(8),
                                N(9))));
 
    write("  preOrder: ");
    tree.backtrackingOrder!(Visit.pre);
    write("\n   inorder: ");
    tree.backtrackingOrder!(Visit.inv);
    write("\n postOrder: ");
    tree.backtrackingOrder!(Visit.post);
    write("\nlevelorder: ");
    tree.levelOrder;
    writeln;
}