Breadth-First Insertion and Traversal in a Binary Tree

traversal_binary_tree.rb

# The traverse iterator will iterate over the tree in the same
# breadth-first order.

class Tree
  attr_accessor :left
  attr_accessor :right
  attr_accessor :data

  def initialize(x=nil)
    @left = @right = nil
    @data = x
  end

  def insert(x)
    list = []
    if @data.nil?
      @data = x
    elsif @left.nil?
      @left = Tree.new x
    elsif @right.nil?
      @right = Tree.new x
    else
      list << @left << @right
      loop do
        node = list.shift
        node.insert(x) and break if node.left.nil?
        list << node.left
        node.insert(x) and break if node.right.nil?
        list << node.right
      end
    end
  end
end

def traverse
  list = []
  yield @data
  list << @left unless @left.nil?
  list << @right unless @right.nil?
  until list.empty?
    node = list.shift
    yield node.data
    list << node.left unless node.left.nil?
    list << node.right unless node.right.nil?
  end
end

items = (1..7).to_a
tree = Tree.new
items.each { |x| tree.insert x }
tree.traverse  { |x| print "#{x} " }
puts