foo.rb

class Tree
  def initialize(*children)
    @children = children
  end

  attr_reader :children

  def each_node1
    return to_enum(:each_node1) unless block_given?

    visit = children.to_a.dup # copy it since we're modifying the array

    until visit.empty?
      current = visit.shift

      catch :skip_children do
        yield current

        current.children.to_a.reverse_each do |child|
          visit.unshift(child)
        end
      end
    end
  end

  def each_node2
    return to_enum(:each_node2) unless block_given?

    visit = children.to_a.reverse # copy it since we're modifying the array

    until visit.empty?
      current = visit.pop

      catch :skip_children do
        yield current
        visit.concat current.children.reverse
      end
    end
  end

  def each_node3(&block)
    return to_enum(:each_node3) unless block_given?

    @children.each do |x|
      yield x
      x.each_node3(&block)
    end
  end

  def inspect
    children.inspect
  end
end

class Leaf
  def initialize(value)
    @value = value
  end

  attr_reader :value

  def children
    []
  end

  def each_node3
    # nop
  end

  def inspect
    @value.inspect
  end
end

def make_tree(min_depth = 2, max_depth = 3, level_width = 250)
  if (min_depth == 0 && rand(2).zero?) || max_depth == 0
    Leaf.new(rand(10))
  else
    Tree.new(*Array.new(level_width) {
               make_tree(min_depth - 1, max_depth - 1, level_width)
             })
  end
end



require "benchmark"

srand 42
tree = make_tree

Benchmark.bmbm do |x|
  x.report("each_node1") { tree.each_node1 { } }
  x.report("each_node2") { tree.each_node2 { } }
  x.report("each_node3") { tree.each_node3 { } }
end

__END__
Rehearsal ----------------------------------------------
each_node1   3.190000   0.040000   3.230000 (  3.223074)
each_node2   2.800000   0.040000   2.840000 (  2.840876)
each_node3   0.880000   0.000000   0.880000 (  0.877915)
------------------------------------- total: 6.950000sec

                 user     system      total        real
each_node1   2.590000   0.000000   2.590000 (  2.590518)
each_node2   2.340000   0.010000   2.350000 (  2.346649)
each_node3   0.870000   0.000000   0.870000 (  0.876887)