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
– tyteen4a03, Commented May 20, 2017 at 20:07
RecurseBST doesn't return anything, so the assignments to self.top.left and self.top.right don't make sense. — nucleon
– nucleon, Commented May 20, 2017 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
– user7422128, Commented May 20, 2017 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
– user7422128, Commented May 20, 2017 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
– FMc, Commented May 20, 2017 at 20:33

score 3 · Accepted Answer · 2017-05-20 22:32:26Z

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

Community · Accepted Answer · 2017-05-23 10:31:35Z

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

YanivR · Accepted Answer · 2017-05-20 21:01:42Z

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)

Collectives™ on Stack Overflow

Binary Search tree recursive implementation in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related