Binary Search tree recursive implementation in python

Question

I'm trying to implement Binary Search tree in python using recursion. I got trapped in some infinite recursions happening in my program.I'm making recursive calls to the function RecursBST by passing address and the data until the top traverse down to None value of either it's left or right child.

class createnode:
 def __init__(self,data):
 self.root=data
 self.left=None
 self.right=None
class createbinarysearchtree:
 def __init__(self, data = None):
 self.top=None 
 def RecursBST(self,top,data): 
 if self.top is None:
 self.top=createnode(data) 
 elif self.top.root>data:
 self.top.left=self.RecursBST(self.top.left,data)
 elif self.top.root<data:
 self.top.right=self.RecursBST(self.top.right,data)
conv=createbinarysearchtree();
conv.RecursBST(conv.top,50)
conv.RecursBST(conv.top,40)

I ran to the below error :

 self.top.left=self.RecursBST(self.top.left,data)
RuntimeError: maximum recursion depth exceeded

• tyteen4a03: Your code never explicitly set what left and right are. Also, what happens when you call RecursBST and data == self.top.root?
• nucleon: RecurseBST doesn't return anything, so the assignments to self.top.left and self.top.right don't make sense.
• user7422128: @nucleon even if I put a return statement as return self.top in the if part I still get the same error.
• user7422128: @tyteen4a03 I think I don't need to explicitly specify left and right as I used it in init. Self.top.root prints me the root value of top node.
• FMc: Typically a BST has three methods: insert(), delete(), and search(). Your current implementation is confusing things by performing insertion-related work (creating a node) with search-related work. Also, there's a related style note that adds to this general confusion: normally classes are things or nouns (BinarySearchTree or Node) not actions (createnode or createbinarysearchtree).

Answer 1

Your code is missing to provide a recursion termination condition and changing the state of the recursion:

From https://en.wikipedia.org/wiki/Recursion_termination

In computing, recursion termination is when certain conditions are met and a recursive algorithm stops calling itself and begins to return values.This happens only if, with every recursive call, the recursive algorithm changes its state and moves toward the base case.

If recursion never ends it MUST then run into maximum recursion depth limit.

The only case you don't run into this problem in your code is when there is no top node, else the recursion is infinite.

There is a nice tool with which you can visualize what your code or the code provided in the other answers does:

http://www.pythontutor.com/

so that you get an impression of what is actually going on and if this is what you intended to achieve.

Here the final result of running the code provided by bones.felipe in the other answer to your question:pythontutor-result-image

The comment to your question provided by FMc gives already a very good answer to the issues you face (citation):

Typically a BST has three methods: insert(), delete(), and search(). Your current implementation is confusing things by performing insertion-related work (creating a node) with search-related work. Also, there's a related style note that adds to this general confusion: normally classes are things or nouns (BinarySearchTree or Node) not actions (createnode or createbinarysearchtree).

Answer 2

I have refactored your classes so that their names make sense (Node, and BST).

I think the main bug on your code is to always reference 'self' and always call from the same instance. If you do that, you are always getting the same data on the node, that is why your recursion never ends, because it is always stucked on the same node. I think it is easier to pass the Node reference as a parameter, and from there make the proper recursive calls, also, you are assigning the left and right variables, but never returning anything. Check the code:

class Node(object):
 def __init__(self, data):
 self.root = data
 self.left = None
 self.right = None
class BST(object):
 def __init__(self):
 self.top = None
 def recursBST(self, node, data): 
 if node is None:
 node = Node(data) 
 elif self.top.root > data:
 node.left = self.recursBST(node.left, data)
 elif self.top.root < data:
 node.right = self.recursBST(node.right, data)
 return node
 def insert(self, data):
 self.top = self.recursBST(self.top, data)
conv = BST()
conv.insert(8)
conv.insert(3)
conv.insert(6)
conv.insert(1)
conv.insert(-1)
conv.insert(10)
conv.insert(14)
conv.insert(50)

Also remeber to add the 'object' on any python class. It is a feature introduced on python 2.7, so it is kind of a bad practice not to include it. Check this for further information.

Bonus: You can check if your insertion algorithms is correct by performing an in-order transversal, after that, the elements should be printed on increasing order (in this case). But that is up to you :)

Answer 3

It looks like you are referring to the same object in each recursive call in: self.RecursBST(self.top.left,data) by using the 'self.top' and not the argument 'top' of the function. Try something like this:

 class createnode:
 def __init__(self,data):
 self.root=data
 self.left=None
 self.right=None
 class createbinarysearchtree:
 def __init__(self, data = None):
 self.top=createnode(data) 
 def RecursBST(self,top,data):
 if top is None:
 return createnode(data)
 if top.root is None:
 top.root=data 
 elif top.root>data:
 top.left=self.RecursBST(top.left,data)
 elif top.root<data:
 top.right=self.RecursBST(top.right,data)