breadth-first tree traversal although the preorder and postorder traversals are common ways of visiting the positions of treeanother common approach is to traverse tree so that we visit all the positions at depth before we visit the positions at depth such an algorithm is known as breadth-first traversal breadth-first traversal is common approach used in software for playing games game tree represents the possible choices of moves that might be made by player (or computerduring gamewith the root of the tree being the initial configuration for the game for examplefigure displays partial game tree for tic-tac-toe figure partial game tree for tic-tac-toewith annotations displaying the order in which positions are visited in breadth-first traversal breadth-first traversal of such game tree is often performed because computer may be unable to explore complete game tree in limited amount of time so the computer will consider all movesthen responses to those movesgoing as deep as computational time allows pseudo-code for breadth-first traversal is given in code fragment the process is not recursivesince we are not traversing entire subtrees at once we use queue to produce fifo ( first-in first-outsemantics for the order in which we visit nodes the overall running time is ( )due to the calls to enqueue and calls to dequeue algorithm breadthfirst( )initialize queue to contain rootwhile not empty do dequeue{ is the oldest entry in the queueperform the "visitaction for position for each child in children(pdo enqueue( {add ' children to the end of the queue for later visitscode fragment algorithm for performing breadth-first traversal of tree