TL;DR — Give your brain a break, and you’ll find the answer.
When I started learning Computer Science Fundamentals (CS Fun) there were a lot of things I didn’t understand. Heck, there are a lot of things I still don’t understand, but back then (I’m speaking, just a few months ago) I felt like I was never going to pick any of it up. At Ada Developers Academy, like with most short term training programs in tech, everything went really quickly. One day we were learning about how to manipulate arrays, and the next it seemed like we were talking about how to build Linked Lists and Directed Graphs!
One of the many data structures we covered in our CS Fun class was the concept of a Binary Tree. It, like most Tree data structures, is normally drawn to look like an upside-down tree, and its defining feature is that each “leaf" node or record has at most 2 children nodes/records. Once we were told what it was, we were to learn how to traverse it and search or data in it. In other words, how to get from node to the next node, and look for information.
This is where Breadth-first Search comes into play. Breadth-First Search says, “I’m going to traverse the tree from the top down, stopping at all nodes on each level to see if they contain the data I’m looking for.” For some reason, my brain could not wrap itself around this concept. I could hear my inner dialogue begin to say, “So, you’re telling me that I’m going to use another data structure called a queue to store nodes, and then read those nodes’ data to find out what the next nodes are and if they have the data I need? Huh?” My head literally hurt trying to work this out.
After a number of tries of only getting as far as, “I know I need a queue to enqueue and dequeue node objects”, I let my brain take a break. It was time to watch a show. My guilty pleasure show of choice at the time was Law & Order: SVU. Now, I admit, that show did kind of stress me out as well, but somehow I was hooked on it.
As I watched episode after episode I discovered that in a number of episodes they would find a suspect they thought might know the person they were looking for. When they found this person they would throw them in jail. Now, because this was a t.v. show they typically could only interview/interrogate one person at a time, usually, in the order they picked them up. A light bulb went off in my head! I finally understood BFS!
The first suspect they found was like the head node of the Binary Tree. The officers threw that first suspect in jail (queued them on the queue) in order to remove them later (dequeue) and find out what they know and who they know. If the suspect isn’t the criminal, then the suspect's known associates are thrown into jail, and then interrogated the same way that the first one was. This continues until the criminal (target node) is found or the case is cold (there are no more nodes to search in the queue).
The brain works in mysterious ways.
Now it’s possible that this analogy didn’t work for you, and that’s okay. Everyone’s brain works a little different. Give yourself a break, and you just might have your “ah, ha” moment. Everyone’s “ah, ha” moments look a little different and come in all shapes and sizes.
If this analogy worked for you and you’d like to see this coded in Ruby, you can see my code below. If the analogy didn’t work for you, but you’d still like to see my breadth-first search coded in Ruby, you can see my code below. (Please be kind in your feedback if you have any. Thank you.) Otherwise, thanks for sticking with me and let me show you the way my brain made it through the code. Best of luck to all of us learning CS Fun!
class Node # what a criminal knowsattr_accessor :value, :left_node, :right_node def initialize(value)
@value = value
@left_node = null
@right_node = null
endend# This node ^^ knows no one because both its children are nullclass Queue # The jail class for new jail creationdef initialize
@queue = Array.new
@queue << item
endenddef 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"