1require "spec_helper"
 2require "ostruct"
 3
 4def bfs(node)
 5  queue = []
 6  queue.push({:node => node, :level => 0})
 7  until (queue.empty?) do
 8    top = queue.shift
 9    p "#{top[:level]} #{top[:node].name}"
10    queue.push({:node => top[:node].left, :level => top[:level]+1}) if top[:node].left
11    queue.push({:node => top[:node].right, :level => top[:level]+1}) if top[:node].right
12  end
13end
14
15describe "bfs" do
16  it "should visit each item" do
17    nailah = OpenStruct.new(:name => "nini", :left => nil, :right => nil)
18    adia = OpenStruct.new(:name => "adia", :left => nil, :right => nil)
19    allison = OpenStruct.new(:name => "alli", :left => adia, :right => nailah)
20    caius = OpenStruct.new(:name => "caius", :left => nil, :right => nil)
21    reeves = OpenStruct.new(:name => "reeves", :left => nil, :right => nil)
22    lisa = OpenStruct.new(:name => "lisa", :left => caius, :right => reeves)
23    sandi = OpenStruct.new(:name => "sandi", :left => allison, :right => lisa)
24    bfs(sandi)
25  end
26end
27