RecursionError in binary tree traversal

Question

I know this has been asked before, but I really don't get what I'm doing wrong. I'm trying to traverse a BST in pre-order fashion. The function below is member of a BST class, which contains self.root. Please help.

def pre_print(self, node=None):
 if not node:
 node = self.root
 print(node.data)
 self.pre_print(node.left)
 self.pre_print(node.right)

It keeps printing 2 or 3 values then I get this error

RecursionError: maximum recursion depth exceeded while calling a Python object
 

• Mark: It's really hard to answer without seeing your class. But guessing, pre_print should be a method on nodes. Then you call it on each child: self.left.pre_print(). Test first that the left or right node is not None.

Answer 1

Since you need some initialization if no node is provided, just add a simple check

def pre_print(self, node=None):
 if not node:
 node = self.root
 print(node.data)
 if node.left:
 self.pre_print(node.left)
 if node.right:
 self.pre_print(node.right)

• Amol Borkar: The function does nothing if I do that, That line is there to use the root node as a starting point if no other node is provided as an argument.

Answer 2

When the recursion arrives at a point in which self==(one of the leafs), I'm assuming its node.left and node.right are ==None, at which point, the next recursion enters the if statement since its node arg is ==None and then sets the ```node==(the self of the leaf node that called this function/method).root).

Which results in this function call being somewhat the similar to the one that was run before it. Resulting in a infinite recursion.

A simple check before entering your method can evade this problem.

def pre_print(self, node=None):
 if not node:
 node = self.root
 print(node.data)
 if node.left : self.pre_print(node.left)
 if node.right: self.pre_print(node.right)