treemap and binary search tree

[python_noobie]

Hello:

I've been attempting to create a treemap (binary search tree) insertion and display function for a bit and am puzzled by the recursive calls. I've tried quite a few things, but the problem seems to be in my mapInsert function. Here's all the code I've written so far in python3:

class EmptyMap():
    """represents an empty map"""

    __slots__ = ()

class NonEmptyMap():
    """represents a non empty map"""

    __slots__ = ('left', 'key', 'value', 'right')


def mkEmptyMap():
    """Constructor: mkEmptyMap() --> EmptyMap"""

    return EmptyMap()

def mkNonEmptyMap (a, b, c, d):
    """constructor:  mkNonEmptyMap:  maptree * key * value * maptree"""

    node = NonEmptyMap()
    node.left = a
    node.key = b
    node.value = c
    node.right = d
    return node

def mapInsert (key, value, map_instance):
    """takes parameters and returns instance of treeMap of NonEmptyMap objects"""


    if isinstance (map_instance, EmptyMap):

        #print ('1 empty  created') #debug
    
        return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())

    elif isinstance (map_instance, NonEmptyMap): #problems start here

        #print (map_instance.left)
        #print (map_instance.right)
        #print(key < map_instance.key)
        
        if map_instance.key > key:

            #print('map_instance key greater than key')

            # recursively insert the given key on the left of the map_instance

           
            return mapInsert(key, value, mkNonEmptyMap(EmptyMap, map_instance.key, map_instance.value, map_instance.left))        
        elif map_instance.key < key:


            return mapInsert(key, value, mkNonEmptyMap(EmptyMap, map_instance.key, map_instance.value, map_instance.right))

        elif map_instance.key == key:

            raise TypeError ('mapInsert:  duplicate keys given')
        
    else:

        raise TypeError ('mapInsert:  non map given for map_instance')

        return

When I run this code, the recursion goes on forever. I'd appreciate any help -- this is a class assignment that I've been struggling with for hours. My questions are: (0) what am I doing wrong in terms of the recursive insertion call and (1) anything else you see that I've missed in the way I've set it up (improperly) would help.

Thanks in advance for taking the time to help me out.

[python_noobie]

Here's the insertion code that I'm trying to run:

smallMap = mapInsert('one', 1,  mapInsert('two', 2, mapInsert('three', 3, mkEmptyMap())))

[python_noobie]

OK, after some more experimentation, I've got it licked. the recursive calls needed to be fixed. they look like this [snippet, not all of the code]:

this is for the mapInsert function

if isinstance (map_instance, EmptyMap):
    
        return mkNonEmptyMap(map_instance, key, value, mkEmptyMap()) 

    elif isinstance (map_instance, NonEmptyMap): 
      
        if map_instance.key > key:
            # we will recursively insert the given key on the left of the map_instance
            
            return mkNonEmptyMap(mapInsert( key, value, map_instance.left) ,     \
                                         map_instance.key,                       \
                                                     map_instance.value, map_instance.right)

fixing the code required making more edits to the other recursive calls. the mistake I was making was (a) in the recursion in the greater than and less than cases, as well when the map_instance was an EmptyMap.