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)