How to create a Tree-based Map with keys

Question

For my intro to computer science class we have a tree based map problem. I'm getting really confused on how to make the tree in the fashion they are asking it.

What I have so far:

class EmptyMap():
    __slots__ = ()

class NonEmptyMap():
    __slots__ = ('left','key','value','right')

def mkEmptyMap():
    m = EmptyMap()
    return m

def mkNonEmptyMap(map1, key, value, map2):
    m = NonEmptyMap()
    m.left = map1
    m.key = key
    m.value = value
    m.right = map2
    return m

def mapInsert(key, value, map1):
   if isinstance(map1, EmptyMap):

   else:

I'm getting stuck on the mapInsert function which is supposed to be recursive. Our tutoring lab doesnt have any tutors in it now so any help is appreciated.

Link to homework file http://www.cs.rit.edu/~vcss241/Homeworks/08/TreeMap-stu.pdf

Thanks!

Answer 1

I have never written or seen Python, but try this:

def mapInsert(key, value, map1):
  if isinstance(map1, EmptyMap):
    return mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())
  else:
    if map1.key == key:
      map1.value = value;
    else if map1.key > key:
      return map1.left = mapInsert(key, value, map1.left)
    else:
      return map1.right = mapInsert(key, value, map1.right)