RecursionError: maximum recursion depth exceeded - Binary Tree

Question

While implementing add_node and search methods for a binary tree, Im getting a RecursionError: maximum recursion depth exceeded

Code:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self, root=None):
        self.root = root

    def add_node(self, node, value):
        node = self.root
        if node is not None:
            if not node.value:
                node.value = value
            elif not node.left:
                node.left = value
            elif not node.right:
                node.right = value
            else:
                node.left = self.add_node(node.left, value)
        else:
            self.root = TreeNode(value)

    def search(self, value):
        node = self.root
        found = False
        while node is not None:
            if node.value == value:
                found = True
            if node.left:
                found = node.left.search(value)
            if node.right:
                found = found or node.left.search(value)
        return found



def main():
    binary_tree = BinaryTree()
    binary_tree.add_node(binary_tree.root, 200)
    binary_tree.add_node(binary_tree.root, 300)
    binary_tree.add_node(binary_tree.root, 100)
    binary_tree.add_node(binary_tree.root, 30)
    binary_tree.traverse_inorder(binary_tree.root)
    print(binary_tree.search(200))


if __name__ == '__main__':
    main()

Error:

Traceback (most recent call last):
  File ".\binary_tree_test20.py", line 51, in <module>
    main()
  File ".\binary_tree_test20.py", line 45, in main
    binary_tree.add_node(binary_tree.root, 30)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  File ".\binary_tree_test20.py", line 22, in add_node
    node.left = self.add_node(node.left, value)
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

I don't understand how add_node is supposed to work. Why are you setting the node's value to itself? Why don't the first three cases use the value parameter at all? — Barmar
– Barmar, Commented Feb 18, 2020 at 6:32
Does add_node really need to take both node and value parameters? It seems like it should just take value, and create the TreeNode object to contain it always. — Barmar
– Barmar, Commented Feb 18, 2020 at 6:32
How are you deciding where to add node in binary tree - left or right? — Poojan
– Poojan, Commented Feb 18, 2020 at 6:41
What's the purpose of the node parameter if you're always replacing it with node = self.root? — Barmar
– Barmar, Commented Feb 18, 2020 at 7:07

torching · Accepted Answer · 2020-02-18 07:17:29Z

This is a remedy I can give you.

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def _add_node(node, value):
    if not node.value:
        node.value = value
    elif not node.left:
        node.left = TreeNode(value)
    elif not node.right:
        node.right = TreeNode(value)
    else:
        _add_node(node.left, value)

class BinaryTree:
    # ...

    def add_node(self, value):
        node = self.root
        if node is not None:
            _add_node(node, value)
        else:
            self.root = TreeNode(value)

    # ...



def main():
    binary_tree = BinaryTree()
    binary_tree.add_node(200)
    binary_tree.add_node(300)
    binary_tree.add_node(100)
    binary_tree.add_node(30)

Although I recommend only extending TreeNode definition without defining BinaryTree.

Barmar · Accepted Answer · 2020-02-18 07:17:32Z

You're getting infinite recursion because you're not using the node parameter, you're replacing it with self.root. So when you recurse, you start at the root again each time, and never end.

Also, the line node.left = self.add_node(node.left, value) expects add_node to return the new node, but your method doesn't return anything. When it's updating an existing node it should just return the modified node; if it's creating a new node, it returns that node.

    def add_node(self, node, value):
        if node is not None:
            if not node.value:
                node.value = value
            elif not node.left:
                node.left = value
            elif not node.right:
                node.right = value
            else:
                node.left = self.add_node(node.left, value)
            return node
        else:
            return TreeNode(value)

You would call this method like this:

binary_tree.root = binary_tree.add_node(binary_tree.root, 30)

Collectives™ on Stack Overflow

RecursionError: maximum recursion depth exceeded - Binary Tree

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related