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.


 
# In this example, we don't encapsulate binary trees as objects; instead, we have a
# convention on how to store them as arrays, and we namespace the functions that
# operate on those data structures.
binary_tree =
  preorder: (tree, visit) ->
    return unless tree?
    [node, left, right] = tree
    visit node
    binary_tree.preorder left, visit
    binary_tree.preorder right, visit
 
  inorder: (tree, visit) ->
    return unless tree?
    [node, left, right] = tree
    binary_tree.inorder left, visit
    visit node
    binary_tree.inorder right, visit
 
  postorder: (tree, visit) ->
    return unless tree?
    [node, left, right] = tree
    binary_tree.postorder left, visit
    binary_tree.postorder right, visit
    visit node
 
  levelorder: (tree, visit) ->
    q = []
    q.push tree
    while q.length > 0
      t = q.shift()
      continue unless t?
      [node, left, right] = t
      visit node
      q.push left
      q.push right
 
do ->
  tree = [1, [2, [4, [7]], [5]], [3, [6, [8],[9]]]]
  test_walk = (walk_function_name) ->
    output = []
    binary_tree[walk_function_name] tree, output.push.bind(output)
    console.log walk_function_name, output.join ' '
  test_walk "preorder"
  test_walk "inorder"
  test_walk "postorder"
  test_walk "levelorder"
 