Two ways of iterating a tree breadth-first in ruby

two_iterators.rb

# We need an iterator to be called on the root node of a tree structure
# The iterator must iterate through the entire first level of the tree
# then the second level, then the third etc.

require 'ostruct'

# First make a tree!
#      1
#     / \
#    2   3
#    |
#    4

node_1 = OpenStruct.new(value: 1)
node_2 = OpenStruct.new(value: 2)
node_3 = OpenStruct.new(value: 3)
node_4 = OpenStruct.new(value: 4)

node_1.children = [node_2, node_3]
node_2.children = [node_4]
node_3.children = []
node_4.children = []

root = node_1

# Breadth first iterators should iterate through level 1 of the tree
# then level 2, then level 3
#
# From this tree we should get the sequence 1, 2, 3, 4

# Breadth-first iterator implementation 1
class BFSIterator1
  include Enumerable
  
  def initialize(root)
    @rt = root
  end
  
  def each(&block)
    iter_each(@rt, &block)
  end
  
  def iter_each(*nodes, &block)
    children = []
    nodes.each do |n|
      block.call n
      children += n.children
    end
    iter_each(*children, &block) if children.any?
  end
end

puts "Testing BFS iterator"
BFSIterator1.new(root).each {|x| puts x.value}

# Breadth-first iterator implementation 2
class BFSIterator2
  def use(node)
    raise "Must be implemented"
  end
  
  def initialize(root)
    @root = root
  end

  def iterate(current = @root, queue = [])
    use(current)
    queue += current.children
    
    return if queue.empty?

    next_item = queue.first
    iterate(next_item, queue.drop(1))
  end
end

class MyIterator < BFSIterator2
  def use(node)
    puts node.value
  end
end

puts "Testing Abstract BFS iterator"
MyIterator.new(root).iterate