binary trees expression tree abstract data type arithmetic expressions can consist of both unary (-an!and binary operators ( bwe only consider expressions containing binary operators and leave the inclusion of unary operators as an exercise binary operators are stored in an expression tree with the left subtree containing the left side of the operation and the right subtree containing the right side we define the expression tree adt below for use with arithmetic expressions consisting of operands comprised of singleinteger digits or single-letter variables define expression tree adt an expression tree is binary tree representation of an arithmetic expression that consists of various operators (+-*/%and operands comprised of single integer digits and single-letter variables within fully parenthesized expression expressiontreeexpstr )builds an expression tree for the expression given in expstr assume the string contains validfully parenthesized expression evaluatevardict )evaluates the expression tree and returns the numeric result the values of the single-letter variables are extracted from the supplied dictionary structure an exception is raised if there is division by zero error or an undefined variable is used tostring ()constructs and returns string representation of the expression the expression tree adt can be used to evaluate basic arithmetic expressions of any size the following example illustrates the use of the adtcreate dictionary containing values for the one-letter variables vars ' ' build the tree for sample expression and then evaluate it exptree expressiontree"( /( - ))print"the result "exptree evaluate(varswe can change the value assigned to variable and reevaluate vars[' ' print"the result "exptree evaluate(varsin the following sections we develop algorithms for constructing and evaluating arithmetic expression trees in order to implement the expressiontree class partial implementation is provided in listing all of the operations will require recursive algorithm that is applied to the tree structure thuseach will call helper method to which the root reference will be passed in order to initiate the recursion if the helper methods were not usedthe client or user code would have to have access to the root reference in order to pass it to the recursive operation