Datas Structures and Algorithms: Depth First Traversal With Recursion (Python)

Data Structures
1

So I’m on part 10 of the DS & A binary tree video where you actually create a depth-first traversal function using recursion I’m doing it in python. Right now, this is the code I have for the function but when I run it, it gives me this recursion error: maximum recursion depth exceeded while calling a Python object.

# CREATES EACH NODE THAT MAKES UP OUR TREE
class Node:
    def __init__(self, value, leftChild=None, rightChild=None):
        self.value = value
        self.leftChild = leftChild
        self.rightChild = rightChild

# CREATES THE TREE WHERE OUR NODES WILL BE HOUSED IN
class Tree:
    # ROOT BY DEFAULT WILL EQUL 'NONE'
    def __init__(self):
        self.root = None
    

    def insert(self, value):
        node = Node(value)
        # IF ROOT EQUALS 'NONE', THEN ROOT WILL POINT TO NODE
        if self.root == None:
            self.root = node
        else:
            # CREATE THE 'CURRENT' VARIABLE AND HAVE IT SET TO THE ROOT POINT AKA, THE VERY TOP NODE
            current = self.root
            while(True):
                if value < current.value:
                    if current.leftChild == None:
                        current.leftChild = node
                        break
                    current = current.leftChild
                else:
                    if current.rightChild == None:
                        current.rightChild = node
                        break
                    current = current.rightChild
    

    def find(self, value):
        current = self.root
        while current != None:
            if value < current.value:
                current = current.leftChild
            elif value > current.value:
                current = current.rightChild
            else:
                return True
        return False


    def traversePreOrder(self, root):
        #VISIT THE ROOT, THEN LEFT, AND LASTLY VISIT RIGHT
        root = self.root
        if root == None:
            return
        print(root.value)
        self.traversePreOrder(root.leftChild)
        self.traversePreOrder(root.rightChild)


tree = Tree()
tree.insert(7)
tree.insert(4)
tree.insert(9)
tree.insert(1)
tree.insert(6)
tree.insert(8)
tree.insert(10)
tree.traversePreOrder(7)

I don’t know what I’m doing wrong to get the error.

2

The mistake is in your preOrderTraversal function at this line:

root = self.root

Since you always set root to self.root you can never leave the loop so it recurses endlessly.

And since we cannot default the parameter in the method definition, we need to differentiate the recursive function from the entry point:

def traversePreOrder(self):
  return self.traversePreOrderRec(self.root)

def traversePreOrderRec(self, root):
  # the rest of your method after
  # root = self.root which you should skip
3

I know this is SUPER LATE (was working on personal projects) but I tried changing it and i’m still getting type errors on my end

    def traversePreOrder(self):
            return self.traversePreOrder(self.root)

    def traversePreOrder(self):
        # VISIT THE ROOT, THEN LEFT, AND LASTLY VISIT RIGHT
        # root = self.root
        if self.root.value == None:
            return
        print(self.root.value)
        self.traversePreOrder(self.root.leftChild)
        self.traversePreOrder(self.root.rightChild)
4

The function cannot have the exact same name. See how I named the second one with “Rec” at the end?