foo.rb

# coding: utf-8

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,
              width_ratio = 1)
  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*width_ratio).to_i)
             })
  end
end

require "benchmark/ips"

srand 42
tree = make_tree

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

  x.compare!
end

__END__
Calculating -------------------------------------
          each_node1     1.000  i/100ms
          each_node2     1.000  i/100ms
          each_node3     1.000  i/100ms
-------------------------------------------------
          each_node1      0.375  (± 0.0%) i/s -      2.000  in   5.338903s
          each_node2      0.405  (± 0.0%) i/s -      3.000  in   7.404513s
          each_node3      1.150  (± 0.0%) i/s -      6.000

Comparison:
          each_node3:        1.2 i/s
          each_node2:        0.4 i/s - 2.84x slower
          each_node1:        0.4 i/s - 3.07x slower