we have already seen common use for the postorder traversalnamely evaluating parse tree look back at our evaluate function above what we are doing is evaluating the left subtreeevaluating the right subtreeand combining them in the root through the function call to an operator assume that our binary tree is going to store only expression tree data let' rewrite the evaluation functionbut model it even more closely on the postorder code def postorder_eval(tree)opers {'+':operator add'-':operator sub'*':operator mul'/':operator truedivres none res none if treeres postorder_eval(tree get_left_child()res postorder_eval(tree get_right_child()if res and res return opers[tree get_root_val()](res res elsereturn tree get_root_val(notice that the form in postorder is the same as the form in postorder_evalexcept that instead of printing the key at the end of the functionwe return it this allows us to save the values returned from the recursive calls in lines and we then use these saved values along with the operator on line the final traversal we will look at in this section is the inorder traversal in the inorder traversal we visit the left subtreefollowed by the rootand finally the right subtree below we show our code for the inorder traversal notice that in all three of the traversal functions we are simply changing the position of the print statement with respect to the two recursive function calls def inorder(tree)if tree !noneinorder(tree get_left_child()print(tree get_root_val()inorder(tree get_right_child()if we perform simple inorder traversal of parse tree we get our original expression backwithout any parentheses let' modify the basic inorder algorithm to allow us to recover the fully parenthesized version of the expression the only modifications we will make to the basic template are as followsprint left parenthesis before the recursive call to the left subtreeand print right parenthesis after the recursive call to the right subtree def print_exp(tree)str_val "if treestr_val '(print_exp(tree get_left_child()str_val str_val str(tree get_root_val()str_val str_val print_exp(tree get_right_child()')return str_val trees and tree algorithms