Tutorial :Python 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,


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.


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.

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Next Post »