figure expression tree for ( (( gobtained by recursively evaluating the left and right subtrees in our examplethe left subtree evaluates to ( cand the right subtree evaluates to (( efg the entire tree therefore represents ( ( )((( efgwe can produce an (overly parenthesizedinfix expression by recursively producing parenthesized left expressionthen printing out the operator at the rootand finally recursively producing parenthesized right expression this general strategy (leftnoderightis known as an inorder traversalit is easy to remember because of the type of expression it produces an alternate traversal strategy is to recursively print out the left subtreethe right subtreeand then the operator if we apply this strategy to our tree abovethe output is +which is easily seen to be the postfix representation of section this traversal strategy is generally known as postorder traversal we have seen this traversal strategy earlier in section third traversal strategy is to print out the operator first and then recursively print out the left and right subtrees the resulting expressiona gis the less useful prefix notationand the traversal strategy is preorder traversalwhich we have also seen earlier in section we will return to these traversal strategies later in the constructing an expression tree we now give an algorithm to convert postfix expression into an expression tree since we already have an algorithm to convert infix to postfixwe can generate expression trees from the two common types of input the method we describe strongly resembles the postfix evaluation algorithm of section we read our expression one symbol at time if the symbol is an operandwe create one-node tree and push pointer to it onto stack if the symbol is an operatorwe pop (pointersto two trees and from the stack ( is popped firstand form new tree whose root is the operator and whose left and right children point to and respectively pointer to this new tree is then pushed onto the stack as an examplesuppose the input is