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')

• brentlance: You are missing a function in your code. Where is mapInsert()?
• Talen Kylon: mapInsert() was a typo by me, it should've been mapInsert1(). Unless you are talking about something else?
• brentlance: Nope, that's it, thanks. Let me take a closer look. Can you be more specific by what you mean by 'the last tree?'
• Talen Kylon: For example, newMap = mapInsert1('one', 1, mapInsert1('two', 2, mkEmptyMap())) --- will build a 'tree' with the key = 'one' and value = 1, but the second 'tree' with a key ='two' and value = 2 is no where to be found.

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'

• Talen Kylon: Thanks Brent! It's funny, everything you mention that I shouldn't do, i've been instructed by my professor to do! (use isinstance, create our own constructors). This will help me though, much appreciated!
• brentlance: Nes, I fixed a pretty big bug in both of our code. You may want to take a second look at the answer if you see this comment.