listing breadth-first traversal on binary tree def breadthfirsttravbintree )create queue and add the root node to it queue enqueuebintree visit each node in the tree while not isempty(remove the next node from the queue and visit it node dequeue(printnode data add the two children to the queue if node left is not none enqueuenode left if node right is not none enqueuenode right in the leaves once constructedan expression tree can be used to evaluate the expression or for converting an infix expression to either prefix or postfix notation the structure of the expression tree is based on the order in which the operators are evaluated the operator in each internal node is evaluated after both its left and right subtrees have been evaluated thusthe lower an operator is in subtreethe earlier it will be evaluated the root node contains the operator to be evaluated figure illustrates several expression trees + + + * * * + - ( ( - ( figure sample arithmetic expression trees while python provides the eval(function for evaluating an arithmetic expression stored as stringthe string must be parsed each time it' evaluated this means the python interpreter has to determine the order in which the operators are evaluated and then perform each of the corresponding operations one way it can do this is with the use of an expression tree after the expression has been parsed and the tree constructedthe evaluation step is quite simpleas you will see later in this section this real-time evaluation of expression strings is not commonly available in compiled languages when using such language and user-supplied expression has to be evaluatedan expression tree can be constructed and evaluated to obtain the result