Python recursion and return statements

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)

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.