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

Your code never explicitly set what `left` and `right` are. Also, what happens when you call `RecursBST` and `data == self.top.root`? — tyteen4a03, May 20 '17 at 20:07
`RecurseBST` doesn't return anything, so the assignments to `self.top.left` and `self.top.right` don't make sense. — nucleon, May 20 '17 at 20:11
@nucleon even if I put a return statement as return self.top in the if part I still get the same error. — user7422128, May 20 '17 at 20:30
@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. — user7422128, May 20 '17 at 20:33
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`). — FMc, May 20 '17 at 20:33
@FMc I'm newbie to programming. Sorry for the confusion. It's a insertion program. — user7422128, May 20 '17 at 20:37
First, you should refactor your code to model the "Node" and "BST" classes properly. Second, You need to add a base case to end the recursion, and finally you are accessing always to "self", keep in mind that no matter the recursion steps you take, "self" is a reference to the same object always, because you are calling self.RecursBST. — bones.felipe, May 20 '17 at 20:51

Claudio · Answer 1 · 2017-05-20T22:32:26.057

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:

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

score 2 · Accepted Answer · edited May 23 '17 at 10:31

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

score 0 · Answer 3 · answered May 20 '17 at 21:01

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)

Binary Search tree recursive implementation in python

3 Answers3