CODEWITHSUNDEEP
pythonrecursioniteration
yttrn
yttrn

Reputation: 11

Maximum recursion with large lists

I am making a binary tree with a very large list, almost 10000 objects. The issue is that I get a maximum recursion error due to the huge size. It happens specifically in the binarytree class where TreeNode is being called to create new objects. I am unsure how to implement this without recursion, as it seems to be the easiest way to implement the code.

class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):
    self.key = key
    self.payload = val
    self.leftChild = left
    self.rightChild = right
    self.parent = parent

def hasLeftChild(self):
    return self.leftChild

def hasRightChild(self):
    return self.rightChild

def isLeftChild(self):
    return self.parent and self.parent.leftChild == self

def isRightChild(self):
    return self.parent and self.parent.rightChild == self

def isRoot(self):
    return not self.parent

def isLeaf(self):
    return not (self.rightChild or self.leftChild)

def hasAnyChildren(self):
    return self.rightChild or self.leftChild

def hasBothChildren(self):
    return self.rightChild and self.leftChild

Binary Tree:

class BinarySearchTree:

def __init__(self):
    self.root = None
    self.size = 0

def length(self):
    return self.size

def __len__(self):
    return self.size

def put(self,key,val):
    if self.root:
        self._put(key,val,self.root)
    else:
        self.root = TreeNode(key,val)
    self.size = self.size + 1

def _put(self,key,val,currentNode):
    if key < currentNode.key:
        if currentNode.hasLeftChild():
               self._put(key,val,currentNode.leftChild)
        else:
               currentNode.leftChild = TreeNode(key,val,parent=currentNode)
    else:
        if currentNode.hasRightChild():
               self._put(key,val,currentNode.rightChild)
        else:
               currentNode.rightChild = TreeNode(key,val,parent=currentNode)

def __setitem__(self,k,v):
   self.put(k,v)

def get(self,key):
   if self.root:
       res = self._get(key,self.root)
       if res:
              return res.payload
       else:
              return None
   else:
       return None

def _get(self,key,currentNode):
   if not currentNode:
       return None
   elif currentNode.key == key:
       return currentNode
   elif key < currentNode.key:
       return self._get(key,currentNode.leftChild)
   else:
       return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
   return self.get(key)

def __contains__(self,key):
   if self._get(key,self.root):
       return True
   else:
       return False

Upvotes: 1

Views: 83

Answers (1)

user2390182
user2390182

Reputation: 73450

It is fairly simple to convert your recursive methods to iterative ones, e.g.:

def get(self, key):
   node = self.root
   while node:
      if node.key == key:
         return node.payload
      elif key < node.key:
         node = node.leftChild
      else:
         node = node.rightChild
   return None

def put(self, key, val):
    if not self.root:
        self.root = TreeNode(key, val)
    else:
        self._put(key, val, self.root)
    self.size = self.size + 1

def _put(self, key, val, currentNode):
    while True:
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                currentNode = currentNode.leftChild
            else:
                currentNode.leftChild = TreeNode(key, val, parent=currentNode)
                break
        else:
            if currentNode.hasRightChild():
                currentNode = currentNode.rightChild
            else:
                currentNode.rightChild = TreeNode(key, val, parent=currentNode)
                break

This gets rid of any recursion (limits) and is just as readable.

Upvotes: 2

Related Questions