Binary Search Tree - Insert Function

Question

Good evening all,

I've been tasked with designing a function in Python that will build a Binary Search tree. When I walk through the function myself, it seems to make perfect sense and it SHOULD work. However, for whatever reason, it's only building the last 'tree' and not saving any of the prior tree information. I've included my classes, the constructors and of course the function. Any tips are appreciated! To test the function, I am using the following line:

newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))


///CODE///
class EmptyMap():
    __slots__ = ()

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

def mkEmptyMap():
    return EmptyMap()

def mkNonEmptyMap(left, key, value, right):
    nonEmptyMap = NonEmptyMap()
    nonEmptyMap.left = left
    nonEmptyMap.key = key
    nonEmptyMap.value = value
    nonEmptyMap.right = right

    return nonEmptyMap

def mapInsert1(key, value, node):
    if isinstance(node, EmptyMap):
        node = mkNonEmptyMap(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            node.value = value
            return mapInsert1(key, value, node)
        else:
            raise TypeError('Bad Map')

Answer 1

Ok, I've got your answer here. There wasn't a problem with your logic, per se, just a problem with how you were trying to implement your algorithm in Python.

And there are several problems with how you're trying to implement your algorithm. The first of these has to do with how variables are passed into functions. I would recommend reading this StackOverflow Question here which discusses how variables are passed into functions Python. The long story short is that due to the way that you are passing and updating variables in your code, you are always updating a local scope copy of the variable, which doesn't actually affect the variable that you want to update.

To see this in your code, try the following:

>>> newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap()))

As you said, this doesn't work. But this does:

>>> newMap = mapInsert1('one', 1, mkEmptyMap())
>>> newMap.right = mapInsert1('two', 2, mkEmptyMap()))

But that's not very helpful, because you have to know what node you want to update before you try and add a new node.

In order to fix your code, what I did was clean up your class implementation. I made the following changes:

1. First, I started using proper constructors. Python classes use the init function as a constructor. See here for more information.
2. Second, I added the insert function. This is what actually solves your problem. Using this function means that you're not overwriting a locally-scoped variable, but instead mutating the outer variable. Again, take a look at the variable-passing question I linked above for more details.
3. Third, I made the empty map just an empty instantiation of the map class, and got rid of the isinstance() check. In Python it's usually best to avoid isinstance whenever possible. Here is more information on avoiding isinstance
4. Fourth, I fixed an infinite loop bug in the code. If you look at the elif key == node.key condition, you are calling mapInsert1 with the same arguments again, which gives you an infinite recursive loop.

Here's the resulting code:

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

    def __init__(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def insert(self, left, key, value, right):
        self.left = left
        self.key = key
        self.value = value
        self.right = right

    def isEmpty(self):
        return self.left == self.right == self.key == self.value == None

def mkEmptyMap():
    return Map(None, None, None, None)

def mapInsert1(key, value, node):
    if node.isEmpty():
        print '0'
        node.insert(mkEmptyMap(), key, value, mkEmptyMap())
        return node
    else:
        if key > node.key:
            print '1'
            return mapInsert1(key, value, node.right)
        elif key < node.key:
            print '2'
            return mapInsert1(key, value, node.left)
        elif key == node.key:
            print '3'
            node.value = value
            return node
        else:
            raise TypeError('Bad Map')

And here's a quick test:

>>> root = mapInsert1('five', 5, mkEmptyMap())
>>> mapInsert1('four', 4, root)
>>> mapInsert1('ace', 1, root)
>>> mapInsert1('five', 'five', root)
>>> root.left.isEmpty()
Out: False
>>> root.left.key
Out: 'ace'
>>> root.left.value
Out: 1
>>> root.right.isEmpty()
Out: False
>>> root.right.key
Out: 'four'
>>> root.right.value
Out: 4
>>> root.key
Out: 'five'
>>> root.value
Out: 'five'