binary trees when leaf node is encounteredwe know it contains an operand but we must determine if that operand is single-integer digitin which case the integer value can be returnedor if it' single-letter variable in the case of the latterthe value for the variable must be located and returned from the user-supplied dictionary for interior nodesthe two subtrees are evaluated by recursively calling the evaltree(function after the two recursive calls returnthe operation represented by the interior node can be computed the computation is performed using the computeop(helper functionwhich performs the appropriate arithmetic operation based on the given operator the implementation of computeop(is left as an exercise the recursive call tree for the evalstr(method is shown in figure when applied to the expression tree from figure + / - figure the recursive call tree for the _evalstr(function tree construction you have seen how an expression tree is usednow let' look at how to construct the tree given an infix expression for simplicitywe assume the following( the expression is stored in string with no white space( the supplied expression is valid and fully parenthesized( each operand will be single-digit or single-letter variableand ( the operators will consist of +-*/and an expression tree is constructed by parsing the expression and evaluating the individual tokens as the tokens are evaluatednew nodes are inserted into the tree for both the operators and operands each set of parentheses will consist of an interior node containing the operator and two childrenwhich may be single valued or subtrees representing subexpressions the process starts with an empty root node set as the current noderoot current suppose we are building the tree for the expression ( * the action taken depends on the value of the current token the first token is left parenthesis