Fix the inorder function of my Python program

Question

0.00/5 (No votes)

See more:

I have this program that needs to print out a red-black tree in python but when I go to run this program, all I get is 65 black. There are other numbers that need to be in the output statement but all I get is the error message "RecursionError: maximum recursion depth exceeded while calling a Python object." I'm not sure haw to fix this. Please help! Thanks!

What I have tried:

Python

class TreeNode:
   def __init__(self,val,left = None,right = None, parent = None,color = None):
      self.val = val
      self.leftChild = left
      self.rightChild = right
      self.parent = parent
      self.color = color
   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))
   
   
class BST(TreeNode):
   def __init__(self):
      self.root = None
      self.size = 0
      self.nil = TreeNode(None)
      self.nil.color = "black"
   def addNode(self,val):
      self.size += 1
      y = self.nil
      x = self.root
      if self.root == None:
         self.root = TreeNode(val,self.nil,self.nil,self.nil,"black")
      else:
         z = TreeNode(val,self.nil,self.nil, None, "red")
         while x!= self.nil:
            y = x
            if z.val < x.val:
               x = x.hasLeftChild()
            else:
               x = x.hasRightChild()
         z.parent = y 
         if y == self.nil:
            self.root = z
         elif z.val < y.val:
            y.leftChild = z
         else:
            y.rightChild = z
         self.treeInsFixer(z)
   def treeInsFixer(self,z):
      while z.parent.color == "red":
         if z.parent == z.parent.parent.leftChild:
            y = z.parent.parent.rightChild
            if y.color == "red":
               z.parent.color = "black"
               y.color = "black"
               z.parent.parent.color = "red"
               z = z.parent.parent
            else:
               if z == z.parent.rightChild:
                  z = z.parent
                  self.leftRotate(z)
               z.parent.color = "black"
               z.parent.parent.color = "red"
               self.rightRotate(z.parent.parent)
         elif z.parent == z.parent.parent.rightChild:
            y = z.parent.parent.leftChild
            if y.color == "red":
               z.parent.color = "black"
               y.color = "black"
               z.parent.parent.color = "red"
               z = z.parent.parent
            else:
               if z == z.parent.leftChild:
                  z = z.parent
                  self.rightRotate(z)
               z.parent.color = "black"
               z.parent.parent.color = "red"
               self.leftRotate(z.parent.parent)
      self.root.color = "black"               
   def leftRotate(self,x):
      y = x.rightChild
      x.rightChild = y.leftChild
      if y.leftChild != self.nil:
         y.leftChild.parent = x
      y.parent = x.parent
      if x.parent == self.nil:
         self.root = y
      elif x == x.isLeftChild():
         x.parent.leftChild = y
      else:
         x.parent.rightChild = y
      y.leftChild = x
      x.parent = y
   def rightRotate(self,x): 
      y = x.leftChild
      x.leftChild = y.rightChild
      if y.rightChild != self.nil:
         y.rightChild.parent = x
      y.parent = x.parent
      if x.parent == self.nil:
         self.root = y 
      elif x == x.isRightChild():
         x.parent.rightChild = y
      else:
         x.parent.leftChild = y
      y.rightChild = x 
      x.parent = y
#This is where the error keeps occuring
   def  inOrder(self,x):
      if x != self.nil:
         self.inOrder(x.leftChild)
         print(x.val, x.color)
         self.inOrder(x.rightChild)

a = BST()
a.addNode(80)
a.addNode(1)
a.addNode(50)
a.addNode(65)
a.addNode(90)
a.inOrder(a.root)

Posted 7-Oct-19 18:22pm

Rema Thomas

Updated 7-Oct-19 21:48pm

Afzaal Ahmad Zeeshan

v2

Add a Solution

Comments

Afzaal Ahmad Zeeshan 8-Oct-19 1:32am

What is the error?

phil.o 8-Oct-19 1:47am

RecursionError: maximum recursion depth exceeded while calling a Python object.

Afzaal Ahmad Zeeshan 8-Oct-19 2:04am

I think that is too bad, if Python cannot handle even small amount of data, don't you think?

OP would need to use an iterative solution to this. :facepalm:

phil.o 8-Oct-19 2:24am

That would be bad not being to handle a small amount of recursion, indeed.
Now remains the need to be sure that it's python's fault :) I can't say, I don't really do python. And I tend to avoid recursion as much as I can, since an iterative way will never cause any stack overflow.

1 solution

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

OriginalGriff · Answer 1 · 2019-10-07T21:49:00

This is going to depend on your data size: Python has a default recursion limit of 999 calls (although that can be changed with Python | sys.setrecursionlimit() method - GeeksforGeeks[^]) unless your test dtaa has 1000 items or more in it - and I doubt that for such early code - increasing the limit will only make you wait a little longer for the error to occur.

Recursion (as I'm sure you know) is when a function calls itself, either directly by using the function name inside the function, or indirectly by calling a function which calls the first function. Sometimes that is what you want, and the classic example is Factorial:

Factorial(n) == n * Factorial(n - 1)

Provided the Factorial function includes a check for "one or below" to terminate the recursion it works well. (An iterative solution is more efficient, but Factorial is often used to demonstrate the concept).
If you omit the termination check though, the Factorial function just continues to call itself until the machine executing it runs out of memory to store where it has to go back to, and the app crashes.
Python restricts that by having a very small limit on how "deep" recursion can go - 999 calls is the default.

Your app is exceeding that default, and unless you have more than 999 items in a single branch of your tree, that means your code is lacking the termination check, or your tree actually has a loop in it.

I'd suggest that you use the debugger[^] to follow exactly what is happening, and work out if it's a code or data problem.

Sorry, but we can't do that for you!

Fix the inorder function of my Python program

1 solution

Solution 1

Add your solution here

Preview 0

Fix the inorder function of my Python program

1 solution

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us