read the operand set the value of the current node to the operand and move up to the parent of the current node read the right parenthesismove up to the parent of the current node since this is the last tokenwe are finished and the expression tree is complete having stepped through the construction of two sample expressionswe now turn our attention to the implementation of the method for building an expression tree throughout the process we have to descend down into the tree to construct each side of an operator and then back up when right parenthesis is encountered but how do we remember where we were in order to back upthere are two approaches we can use one involves the use of stack and the other recursion in you saw that backtracking is automatically handled by the recursion as the recursive calls unwind given this simplicitywe implement recursive function to build an expression treeas shown in listing listing constructing an expression tree class expressiontree def _buildtreeselfexpstr )build queue containing the tokens in the expression string expq queue(for token in expstr expq enqueuetoken create an empty root node self _exptree _exptreenodenone call the recursive function to build the expression tree self _recbuildtreeself _exptreeexpq recursively builds the tree given an initial root node def _recbuildtreeselfcurnodeexpq )extract the next token from the queue token expq dequeue(see if the token is left paren'(if token ='(curnode left _exptreenodenone buildtreereccurnode leftexpq the next token will be an operatorcurnode data expq dequeue(curnode right _exptreenodenone self _buildtreereccurnode rightexpq the next token will be )remove it expq dequeue(otherwisethe token is digit that has to be converted to an int else curnode element token