trees in this grammar the first and second productions have an expression composed of an expressionfollowed by another expressionfollowed by an addition or multiplication token if we tried to write recursive function for this grammarthe base case would not come first the recursive case would come first and hence the function would not be written correctly since the base case must come first in recursive function this type of production is called left-recursive rule grammars with left-recursive rules are not suitable for top-down construction of parser there are other ways to construct parsers that are beyond the scope of this text you can learn more about parser construction by studying book on compiler construction or programming language implementation binary search trees binary search tree is tree where each node has up to two children in additionall values in the left subtree of node are less than the value at the root of the tree and all values in the right subtree of node are greater than or equal to the value at the root of the tree finallythe left and right subtrees must also be binary search trees this definition makes it possible to write class where values may be inserted into the tree while maintaining the definition the code in sect accomplishes this the binarysearchtree class class binarysearchtree this is node class that is internal to the binarysearchtree class class __node def __init__(self,val,left=none,right=none) self val val self left left self right right def getval(self)return self val def setval(self,newval) self val newval def getleft(self)return self left def getright(self)return self right def setleft(self,newleft) self left newleft def setright(self,newright) self right newright this method deserves little explanation it does an inorder traversal of the nodes of the tree yielding all the values in this waywe get this copy belongs to 'acha