You’ve learned how to climb from the top to the bottom of the tree, exploring all the leaves first before climbing back down each level. Now let’s learn how to explore each level (depth) of a tree before moving on to the next level, eventually reaching the leaves.
Traditionally this challenge is tackled using a Queue. As you recall from our lesson on Queues, it is a linear data structure following a First-In-First-Out (FIFO) protocol. For this exercise, you will be using an Array to replicate the queue and taking advantage of the Array method removeFirst(_:) to follow the FIFO logic instead of adding your own Queue class.
Breadth-first traversal starts by adding the root to the queue, then it enters a while loop that runs while the queue is not empty. Each iteration of the while loop starts by dequeuing the first element off the queue and ends the loop by adding the children of the dequeued node to the end of the queue. In between those two actions, the dequeuing and the appending, it is up to you to decide what action to take. In this exercise, we will simply print out the node that was dequeued so that we can follow the logic of the traversal.
Instructions
Create a new function underneath your depth-first traversal, called breadthFirstTraversal(). It shouldn’t have any parameters and leave the body blank for now.
Inside the function create a variable, queue, and initialize an array of TreeNodes. Remember the syntax will require you to call the Array initializer. Try it yourself first and then check the hint for how we implemented this.
Append the root variable to the queue, this starts the breadth-first sequence.
Create an empty while loop that continues until the queue is NOT empty on the next line.
Inside the while loop:
- Create a new constant,
currentNodeand set it equal toqueue.removeFirst(). - Print the
currentNodeand a space (same as in the DFS method, use theSwift.print(_:separator:terminator:)). - Append the children of the
currentNodeto the queue using theappend(contentsOf:)array method version of Swift’s arrayappendmethod.
Near the end of the file you will see a comment about Breadth First Traversal, below this, make a call to .breadthFirstTraversal on familyTree.
Uncomment the last three lines of code and compare your breadth-first printing to the depth-first printing and the standard tree printing. Can you think of any scenarios where one type of traversal may be preferred over another?
As an additional challenge, try replacing the Array implementation of the queue with your queue from previous lessons. It may take some playing around with so your best bet might be to do it in a new Playground in Xcode (if you’re familiar with it) on your computer.