Recursion and return statements

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.

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

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

Method 2

You are inside a function and want to return a value, what do you do? You write

def function():
    return value

In your case you want to return the value returned by a function call, so you have to do.

def function():
    return another_function()

However you do

def function():
    another_function()

Why do you think that should work? Of course you use recursion but in such a case you should remember the Zen of Python which simply says:

Special cases aren’t special enough to break the rules.

Method 3

You need a return statement in your recursive case. Try this adjustment.

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
            return self.insert(key, root=tmp.right)
        elif key < tmp.key: # we work with the left subtree
            return self.insert(key, root=tmp.left)
        else: # key already exists
            return 0

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0