Maximum recursion depth exceeded error in Python while implementing Binary Search Tree

Question

I was using Python to learn BST and tried implementing insert and find methods. But I was getting Maximum recursion depth exceeded error in insertNode method. I am new to BST data structure and hence struggling to implement the methods in Python. I tried researching and making my code similar to ones on the internet, but I am still getting the error.

class Node:
def __init__(self,data):
 self.data = data
 self.left = None
 self.right = None
class BST:
 def __init__(self):
 self.root = None 
 def insert(self,data):
 temp = Node(data)
 if self.root is None:
 self.root = temp
 else:
 self.insertNode(self.root,data) 
 def insertNode(self,root,data):
 temp = Node(data)
 if data < self.root.data:
 if self.root.left is None:
 self.root.left = temp
 else:
 self.insertNode(self.root.left,data)
 elif data > self.root.data:
 if self.root.right is None:
 self.root.right = temp
 else:
 self.insertNode(self.root.right,data)
 def findinTree(self,root,data):
 if self.root is None:
 return False
 if data == self.root.data:
 return True
 if data < self.root.data:
 self.findinTree(self.root.left,data)
 else:
 self.findinTree(self.root.right,data)
 return False
bst = BST()
bst.insert(30)
bst.insert(10)
bst.insert(50)
bst.insert(90)
bst.insert(100)
bst.insert(15)

Please help debug the error so that the functions work as intended.

• ShreyasG: What is the exact error and on what line does it occur? Can you paste the error trace here?
• Jacobr365: you could increase the recursion limit with sys.setrecursionlimit. just be careful, python stackframes can get pretty big.
• Shrijan Aryal: Traceback (most recent call last): File "python", line 47, in <module> File "python", line 16, in insert File "python", line 29, in insertNode File "python", line 29, in insertNode File "python", line 29, in insertNode File "python", line 29, in insertNode File "python", line 19, in insertNode RuntimeError: maximum recursion depth exceeded @ShreyasG
• quamrana: Please update your question with the stack trace - it will be easier to read. Also I can see problems in your code, for instance in: def insertNode(self,root,data): you have a root parameter which you don't use inside the method.
• VPfB: Also, you are creating way too many temp Nodes. You could create a Node only when really needed.

Answer 1

In insertNode you refer to self.root which is the tree's root. Instead, you should refer root, the function parameter.

In fact, after the 1st sub-level is created (bst.insert(50)), the right branch of the tree's root is not None anymore and so it keeps calling self.insertNode(self.root.right,data)

def insertNode(self,root,data): 
 temp = Node(data) 
 if data < root.data: 
 if root.left is None: 
 print("Inserting {} on the left branch of {}".format(data, root.data)) 
 root.left = temp 
 else: 
 print("Inserting {} on the left branch of {}".format(data, root.data)) 
 self.insertNode(root.left,data) 
 elif data > root.data: 
 if root.right is None: 
 print("Inserting {} on the right branch of {}".format(data, root.data)) 
 root.right = temp 
 else: 
 print("Inserting {} on the right branch of {}".format(data, root.data)) 
 self.insertNode(root.right,data) 

• Andy Dent: General programming advice - do NOT use the same name for a function parameter as for an object property. It's too easy to make the mistake which Daniele Bacarella has caught.

Answer 2

These methods might be the root ;-) cause of the problem:

def insertNode(self, root, data):
 if data < root.data: # <- use the root parameter ...
 if root.left is None:
 root.left = Node(data)
 else:
 self.insertNode(root.left, data)
 else:
 if root.right is None:
 root.right = Node(data)
 else:
 self.insertNode(root.right, data)
def findinTree(self, root, data):
 if root is None:
 return False
 if data == root.data:
 return True
 if data < root.data:
 return self.findinTree(root.left, data)
 else:
 return self.findinTree(root.right, data)

NB code not tested

Update: took suggestion of VPfB and did not create unnecessary nodes.

• Shrijan Aryal: Thank you but I also have another question. If I am making "findinTree" method this way, how would I pass in the parameter "root" while calling this method via object ?
• quamrana: The same way you've done the insert method. You write yourself a find wrapper method. Any upvotes or accepted answer would be much appreciated.