python - Recursion and return statements

Question

I'm fairly new to Python and recursive functions as a whole, so pardon my ignorance.

I am trying to implement a binary search tree in Python and have the following insert method (taken out of a class):

def insert(self, key, root=None):
    '''Inserts a node in the tree'''
    if root == None:
        root = self.root
    if root.key == None:
        self._update(root, key)
        return 0
    else:
        tmp = root
        if key > tmp.key: # we work with the right subtree
            self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            self.insert(key, root=tmp.left)
        else: # key already exists
            return 0

I'm not sure if this is legible, but it traverses the tree until it gets to a None value and updates the node with the key to insert.

Now, the method works nicely and correctly creates a BST from scratch. But there's a problem with the return statements, as it only returns 0 if there is no recursion performed.

>>> bst.insert(10)
0
>>> bst.insert(15)
>>> bst.root.right.key
15
>>>

"Inserting" the root key again returns 0 (from line 15) the way it should.

>>> bst.insert(10)
0

I can't figure out why this happens. If I put a print statement in line 6, it executes correctly, yet it just won't return anything past the first insertion. Why is this? (I'm pretty sure I'm missing some basic information regarding Python and recursion)

Thanks for your help,

Ivan

P.S.: I've read that recursion is not the best way to implement a BST, so I'll look into other solutions, but I'd like to know the answer to this before moving on.

Answer 1

On your recursive lines, you do not return anything. If you want it to return 0, you should replace them with lines like:

return self.insert(key, root=tmp.left)

instead of just

self.insert(key, root=tmp.left)