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 btree := [1, [2, [4, [7, null, null],
                         null],
                     [5, null, null]],
                 [3, [6, [8, null, null],
                         [9, null, null]],
                     null]]
 
def backtrackingOrder(node, pre, mid, post) {
    switch (node) {
        match ==null {}
        match [value, left, right] {
            pre(value)
            backtrackingOrder(left, pre, mid, post)
            mid(value)
            backtrackingOrder(right, pre, mid, post)
            post(value)
        }
    }
}
 
def levelOrder(root, func) {
    var level := [root].diverge()
    while (level.size() > 0) {
        for node in level.removeRun(0) {
            switch (node) {
                match ==null {}
                match [value, left, right] {
                    func(value)
                    level.push(left)
                    level.push(right)
}   }   }   }   }
 
print("preorder:   ")
backtrackingOrder(btree, fn v { print(" ", v) }, fn _ {}, fn _ {})
println()
 
print("inorder:    ")
backtrackingOrder(btree, fn _ {}, fn v { print(" ", v) }, fn _ {})
println()
 
print("postorder:  ")
backtrackingOrder(btree, fn _ {}, fn _ {}, fn v { print(" ", v) })
println()
 
print("level-order:")
levelOrder(btree, fn v { print(" ", v) })
println()