Question 5: Binary Tree Breadth-First Traversal (applying a queue to solve a problem)

In a breadth-first traversal, we visit a node, then all the nodes on the next level from left to right, then all nodes on the 3rd level ( from left to right) etc. For example, in the tree below, a breadth-first traversal would visit the nodes in the following order: a, b, c, d, e, f, g, h, i, j, k, l 1) Write (on paper) a method to perform a breadth-first search traversal. As you visit each node, just print out its item. You can assume that this method has access to the instance variable 'root'. Use a queue in your solution (the algorithm is non-recursive). 2) What is the time complexity ( in big-O notation) for this method? Explain how you determined this. Just giving me the correct O() answer will only be half credit.