Building BST Recursion Depth Exceeded

Question

New here, so apologies for any broken decorum. I'm trying to write code for a BST that has a method that builds the BST using a sorted array. I keep getting the RecursionError: Maximum recursion depth exceeded. First time posting because I feel so lost :( Appreciate any help.

class Node:

    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

class BinarySearchTree:

    def __init__(self, sorted_array):
        self.root = None
        self.sorted_array=sorted_array


    def build_tree(self, sorted_array):
        if not self.sorted_array:
            return None
        mid = len(sorted_array) // 2
        root = Node(self.sorted_array[mid])
        root.left = self.build_tree(self.sorted_array[0:mid])
        root.right = self.build_tree(self.sorted_array[mid + 1:])
        return root

example_array=[1, 3, 4, 5, 7, 8, 9, 23, 67, 324, 6345]

my_tree=BinarySearchTree()

my_tree.build_tree(example_array)

MAK · Answer 1 · 2021-05-10T04:13:18.093

1

Inside your build_tree method, sorted_array and self.sorted_array are not the same object. You can fix this by using sorted_array everywhere, there does not appear to be any reason to keep a self reference anyway.

It might be helpful to use a debugger to step through the code to figure out problem like this.

edited May 10 '21 at 04:13

answered Apr 16 '21 at 00:17

MAK

26,140
11
55
86

score 0 · Answer 2 · answered Apr 16 '21 at 09:32

i am not so much aware of Python syntax, though I can smell something messy here :

    root.left = self.build_tree(self.sorted_array[0:mid])

you can't always start slicing from 0 (0 is not constant), rather you can use following modification in your code, which will iterate current start position of the array:

    root.left = self.build_tree(self.sorted_array[:mid])

you can learn more about python slicing from this thread.

Building BST Recursion Depth Exceeded

2 Answers2