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.


 
class Node(T)
  property left : Nil | Node(T)
  property right : Nil | Node(T)
  property data : T
 
  def initialize(@data, @left = nil, @right = nil)
  end
 
  def preorder_traverse
    print " #{data}"
    if left = @left
      left.preorder_traverse
    end
    if right = @right
      right.preorder_traverse
    end
  end
 
  def inorder_traverse
    if left = @left
      left.inorder_traverse
    end
    print " #{data}"
    if right = @right
      right.inorder_traverse
    end
  end
 
  def postorder_traverse
    if left = @left
      left.postorder_traverse
    end
    if right = @right
      right.postorder_traverse
    end
    print " #{data}"
  end
 
  def levelorder_traverse
    queue = Array(Node(T)).new
    queue << self
 
    until queue.size <= 0
      node = queue.shift
 
      unless node
        next
      end
 
      print " #{node.data}"
 
      if left = node.left
        queue << left
      end
      if right = node.right
        queue << right
      end
    end
  end
end
 
tree = Node(Int32).new(1,
  Node(Int32).new(2,
    Node(Int32).new(4,
      Node(Int32).new(7)),
    Node(Int32).new(5)),
  Node(Int32).new(3,
    Node(Int32).new(6,
      Node(Int32).new(8),
      Node(Int32).new(9))))
 
print "preorder:   "
tree.preorder_traverse
print "\ninorder:    "
tree.inorder_traverse
print "\npostorder:  "
tree.postorder_traverse
print "\nlevelorder: "
tree.levelorder_traverse
puts
 
 