tree_kata.rb

# A programming kata, to exercise code skills
# around tree traversal.  Which, if you don't
# do it often, can get rusty. ;).

class Node
  attr_accessor :val, :left, :right
  def initialize(val)
    self.val = val
  end
end

#             1
#        2          3
#     4    5     6     7
#   8  9 10 11 12 13 14 15
root = Node.new(1).tap do |n|
  n.left = Node.new(2).tap do |n|
    n.left  = Node.new(4).tap do |n|
      n.left  = Node.new(8)
      n.right = Node.new(9)
    end
    n.right = Node.new(5).tap do |n|
      n.left  = Node.new(10)
      n.right = Node.new(11)
    end
  end
  n.right = Node.new(3).tap do |n|
    n.left = Node.new(6).tap do |n|
      n.left  = Node.new(12)
      n.right = Node.new(13)
    end
    n.right = Node.new(7).tap do |n|
      n.left  = Node.new(14)
      n.right = Node.new(15)
    end
  end
end

# Algorithm starts here.
row      = [ root ]
reversed = false

loop do
  break if row.empty?
  vals = row.map(&:val)
  vals = vals.reverse if reversed
  print vals.join(' ') + ' '
  row = row.map { |n| [n.left, n.right].compact }.flatten
  reversed = !reversed
end
puts