the current node is not leaf nodelook up the operator in the current node and apply it to the results from recursively evaluating the left and right children to implement the arithmeticwe use dictionary with the keys '+''-''*'and '/the values stored in the dictionary are functions from python' operator module the operator module provides us with the functional versions of many commonly used operators when we look up an operator in the dictionarythe corresponding function object is retrieved since the retrieved object is functionwe can call it in the usual way function(param ,param so the lookup opers['+']( , is equivalent to operator add( , import operator def evaluate(parse_tree)opers {'+':operator add'-':operator sub'*':operator mul'/':operator truedivleft parse_tree get_left_child(right parse_tree get_right_child(if left and rightfn opers[parse_tree get_root_val()return fn(evaluate(left),evaluate(right)elsereturn parse_tree get_root_val(finallywe will trace the evaluate function on the parse tree we created in figure when we first call evaluatewe pass the root of the entire tree as the parameter parse_tree then we obtain references to the left and right children to make sure they exist the recursive call takes place on line we begin by looking up the operator in the root of the treewhich is '+the '+operator maps to the operator add function callwhich takes two parameters as usual for python function callthe first thing python does is to evaluate the parameters that are passed to the function in this case both parameters are recursive function calls to our evaluate function using left-to-right evaluationthe first recursive call goes to the left in the first recursive call the evaluate function is given the left subtree we find that the node has no left or right childrenso we are in leaf node when we are in leaf node we just return the value stored in the leaf node as the result of the evaluation in this case we return the integer at this point we have one parameter evaluated for our top-level call to operator add but we are not done yet continuing the left-to-right evaluation of the parameterswe now make recursive call to evaluate the right child of the root we find that the node has both left and right child so we look up the operator stored in this node'*'and call this function using the left and right children as the parameters at this point you can see that both recursive calls will be to leaf nodeswhich will evaluate to the integers four and five respectively with the two parameters evaluatedwe return the result of operator mul( at this point we have evaluated the operands for the top level '+operator and all that is left to do is finish the call to operator add( the result of the evaluation of the entire expression tree for ( ( )is binary tree applications