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.


def preorder;
preorder = { Node node ->
    ([node] + node.children().collect { preorder(it) }).flatten()
}
 
def postorder;
postorder = { Node node ->
    (node.children().collect { postorder(it) } + [node]).flatten()
}
 
def inorder;
inorder = { Node node ->
    def kids = node.children()
    if (kids.empty) [node]
    else if (kids.size() == 1 &&  kids[0].'@right') [node] + inorder(kids[0])
    else inorder(kids[0]) + [node] + (kids.size()>1 ? inorder(kids[1]) : [])
}
 
def levelorder = { Node node ->
    def nodeList = []
    def level = [node]
    while (!level.empty) {
        nodeList += level
        def nextLevel = level.collect { it.children() }.flatten()
        level = nextLevel
    }
    nodeList
}
 
class BinaryNodeBuilder extends NodeBuilder {
    protected Object postNodeCompletion(Object parent, Object node) {
        assert node.children().size() < 3
        node
    }
}