Data Structures & Algorithms in Ruby: Breadth-First Search for Binary Trees
Last week, we implemented a #find method for our Binary Search Tree which returned the Boolean true/false indicating whether our value was found or not. What if we wanted to return all the nodes in our Binary Search Tree? Look at a representation of any Binary Tree (it doesn’t even have to be a Binary Search Tree). If you were asked to write some code to return all the values in this binary tree while visiting each node only once, how would you do it? We are going to see that there are many different ways to traverse a tree, and the first algorithm that we will learn to do this is the Breadth-First Search algorithm.
According to Introduction to Algorithms, Third Edition (Cormen et al., 2009, p. 594) “Breadth-first search is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Prim’s minimum-spanning-tree algorithm and Dijkstra’s single-source shortest-paths algorithm use ideas similar to those in breadth-first search.”
In a Breadth-First Search (BFS), all the nodes of a tree are returned by beginning first at the root node, then exploring the root node’s children before moving on to explore the children of the root node’s children. It can be visualized by picturing all the nodes on the tree begin returned in a horizontal order (hence…
