Answer must be in python

Consider the example of a breadth-first traversal given in Figure 8.17. Using the annotated numbers from that figure, describe the contents of

the queue before each pass of the while loop in Code Fragment 8.14. To get started, the queue has contents {1} before the first pass, and contents {2,3,4} before the second pass.

Code fragment and figure below

Algorithm breadthfirst(T):

Initialize queue Q to contain T.root( )

while Q not empty do

p = Q.dequeue( ) {p is the oldest entry in the queue}

perform the visit action for position p

for each child c in T.children(p) do

Q.enqueue(c) {add ps children to the end of the queue for later visits}

Code Fragment 8.14: Algorithm for performing a breadth-first traversal of a tree.

OIX Figure 8.17: Partial game tree for Tic-Tac-Toe, with annotations displaying the or OIX Figure 8.17: Partial game tree for Tic-Tac-Toe, with annotations displaying the or