binary trees breadth-first traversal the preorderinorderand postorder traversals are all examples of depth-first traversal that isthe nodes are traversed deeper in the tree before returning to higher-level nodes another type of traversal that can be performed on binary tree is the breadth-first traversal in breadth-first traversalthe nodes are visited by levelfrom left to right figure shows the logical ordering of the nodes in breadth-first traversal of the example tree ii jj figure the logical ordering of the nodes with breadth-first traversal recursion cannot be used to implement breadth-first traversal since the recursive calls must follow the links that lead deeper into the tree insteadwe must devise another approach your first attempt might be to visit node followed by its two children thusin the example tree we would visit node followed by nodes and cwhich is the correct ordering but what happens when we visit node bwe can' visit its two childrend and euntil after we have visited node what we need is way to remember or save the two children of until after has been visited likewisewhen visiting node cwe will have to save its two children until after the children of have been visited after visiting node cwe have saved four nodes--defand --which are the next four to be visitedin the order they were saved the best way to save node' children for later access is to use queue we can then use an iterative loop to move across the tree in the correct node order to produce breadth-first traversal listing uses queue to implement the breadth-first traversal the process starts by saving the root node and in turn priming the iterative loop during each iterationwe remove node from the queuevisit itand then add its children to the queue the loop terminates after all nodes have been visited expression trees arithmetic expressions such as ( + )*( - can be represented using an expression tree an expression tree is binary tree in which the operators are stored in the interior nodes and the operands (the variables or constant valuesare stored