Law & Order Helped Me Understand BFS (Breadth-First Search)

Binary Tree from commons.wikimedia.org
class Node # what a criminal knowsattr_accessor :value, :left_node, :right_node    def initialize(value)
@value = value
@left_node = null
@right_node = null
end
end# This node ^^ knows no one because both its children are nullclass Queue # The jail class for new jail creationdef initialize
@queue = Array.new
end

def enqueue(item)
@queue << item
end

def dequeue
@queue.shift
end

def empty?
@queue.empty?
end
enddef breadth_first_search (first_suspect_node, target_value) new_node_jail = Queue.new new_node_jail.enqueue(first_suspect_node) while !new_node_jail.empty

suspect_node = queue.deq

if suspect_node.value == target_value
return suspect_node # you've found your criminal
end
# if the suspect_node has nodes that it knows, enqueue them
new_node_jail.enqueue(suspect_node.left) if suspect_node.left
new_node_jail.enqueue(suspect_node.right) if suspect_node.right
end

return "No criminal found"
end

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kate Pond

Kate Pond

I’m part developer, part interpretive park ranger, & 100% awesome! I’m always learning, and I love it!