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.


T Node
   Int data
   Node? left
   Node? right
 
   F (data, Node? left = N, Node? right = N)
      .data = data
      .left = left
      .right = right
 
   F preorder(visitor) -> N
      visitor(.data)
      I .left != N
         .left.preorder(visitor)
      I .right != N
         .right.preorder(visitor)
 
   F inorder(visitor) -> N
      I .left != N
         .left.inorder(visitor)
      visitor(.data)
      I .right != N
         .right.inorder(visitor)
 
   F postorder(visitor) -> N
      I .left != N
         .left.postorder(visitor)
      I .right != N
         .right.postorder(visitor)
      visitor(.data)
 
   F preorder2(&d, level = 0) -> N
      d[level].append(.data)
      I .left != N
         .left.preorder2(d, level + 1)
      I .right != N
         .right.preorder2(d, level + 1)
 
   F levelorder(visitor)
      DefaultDict[Int, [Int]] d
      .preorder2(&d)
      L(k) sorted(d.keys())
         L(v) d[k]
            visitor(v)
 
V tree = Node(1,
              Node(2,
                   Node(4,
                        Node(7, N, N),
                        N),
                   Node(5, N, N)),
              Node(3,
                   Node(6,
                        Node(8, N, N),
                        Node(9, N, N)),
                   N))
 
F printwithspace(Int i)
   print(‘#. ’.format(i), end' ‘’)
 
print(‘  preorder: ’, end' ‘’)
tree.preorder(printwithspace)
print()
print(‘   inorder: ’, end' ‘’)
tree.inorder(printwithspace)
print()
print(‘ postorder: ’, end' ‘’)
tree.postorder(printwithspace)
print()
print(‘levelorder: ’, end' ‘’)
tree.levelorder(printwithspace)
print()