отсортированный массив / список в сбалансированное двоичное дерево поиска

Question

class Node:
   
    def __init__(self, data, left_child=None, right_child=None):
        self.data = data
        self.left_child = left_child
        self.right_child = right_child
        self.height = 0 
class BinarySearchTree:
    ''' defines a Binary Search Tree data structure '''
    def __init__(self):
        ''' initialized the tree as empty '''
        self.root = None
    def add(self, data):
        ''' add a new element (which contains data) to the tree '''
        self.root = self.add_helper(self.root, data)

    def add_helper(self, cursor, data):
        ''' recursive helper of add() '''
       
        #base case
        if cursor is None:
            return Node(data)

        if data == cursor.data:
            print("duplicate")

        if data < cursor.data:
            cursor.left_child = self.add_helper(cursor.left_child, data)
        else:
            cursor.right_child = self.add_helper(cursor.right_child, data)

        cursor.update_height()

        return cursor

    def rebalance_tree(self):
        arr = self.inorder()
        return self.rebalance_tree_helper(arr)

    def rebalance_tree_helper(self, arr):
        if not arr:
            return None

        mid = (len(arr)) // 2

        root = Node(arr[mid])

        self.root.left_child = self.rebalance_tree_helper(arr[:mid])

        self.root.right_child = self.rebalance_tree_helper(arr[mid + 1:])

        return root

Итак, это двоичное дерево поиска работает совершенно нормально, но когда я попытался добавить метод баланса, по этой ссылке здесь: https://www.geeksforgeeks.org/sorted-array-to-balanced-bst/#: ~: text = Следуя% 20is% 20a% 20simple% 20algorithm, root% 20created% 20in% 20step% 201 .

Essentaily У меня есть список / массив из моего метода inorder (), и я пытаюсь использовать его в качестве параметра моего метода balance () , и вернуть сбалансированный список. Все должно работать правильно, но индекс списка выходит за пределы допустимого диапазона. Я запустил его в отладчике, и он получил необычный результат. Это список, который намного меньше, чем должен быть. Вот результат из списка, который должен быть:

data = sample(range(1, 100), k=126)
binarysearchtree = BinarySearchTree()
seed(50)
data = sample(range(1, 4000), k=126)
data.sort()
for x in data:
    bst.add(x)

bst.rebalance_tree()

tree_data = list(bst.inorder())
print(tree_data)
print(data)

это результат:

[3964, 5, 3298]
[5, 58, 166, 256, 258, 303, 330, 374, 383, 389, 405, 413, 447, 512, 571, 573, 584, 602, 783, 833, 838, 895, 909, 978, 1000.....]

первый список - это сбалансированный двоичный список .. и он имеет только 3 входа