Maximum recursion depth exceeded when finding the depth of binary-search-tree

Question

This is my code:

# increase the limit of recursion
import sys
sys.setrecursionlimit(100000)
import numpy as np

# make binary search tree from list
def bst_build(seq):
    binary_search_tree = [seq[0], None, None]
    seq.pop(0)

    def add_child(main, sub):
        if len(sub) != 0:
            if main[0] > sub[0]:
                if main[1] == None:
                    main.pop(1)
                    main.insert(1, [sub[0], None, None])
                    sub.pop(0)
                    add_child(binary_search_tree, sub)
                else:
                    add_child(main[1], sub)
            
            elif main[0] < sub[0]:
                if main[2] == None:
                    main.pop(2)
                    main.insert(2, [sub[0], None, None])
                    sub.pop(0)
                    add_child(binary_search_tree, sub)        
                else:
                    add_child(main[2], sub)
            else:
                sub.pop(0)         
        else:
            pass

    add_child(binary_search_tree, seq)

    return binary_search_tree

# check the correctness
def bst_check(b):
    if b is None: return True
    if b[1] is not None:
        if b[1][0] >= b[0]: return False
        if bst_check(b[1]) == False: return False
    if b[2] is not None:
        if b[2][0] <= b[0]: return False
        if bst_check(b[2]) == False: return False
    return True

# find depth of binary search tree
def bst_depth(b):
    maximum_depth = 0
    current_depth = 0

    def find_depth(tree):
        nonlocal maximum_depth
        nonlocal current_depth

        if len(tree) != 1:
            if tree[1] != None and len(tree[1]) != 1:
                current_depth += 1
                find_depth(tree[1])
            else:
                tree.pop(1)
                if maximum_depth <= current_depth:
                    maximum_depth = current_depth
                current_depth = 0
                find_depth(b)
        else:
            pass  
    find_depth(b)      

    return maximum_depth

unsorted = list(np.random.randint(0,100,10))
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(t1)
print(t2)

print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

First, I make a binary search tree from a list, and check whether it is a binary search tree.

The first element of given list is the root node, and following elements become the child nodes. None is appended to leaf nodes.

For example, the result of calling bst_build([4, 2, 1, 3, 6, 5, 7]) is:

[4, 
  [2, 
    [1, None, None], 
    [3, None, None]
  ], 
  [6, 
    [5, None, None],
    [7, None, None]]
  ]
]

The result is a binary search tree because the left child node is smaller than the parent node and the right child node is larger than the parent node. Therefore the result of calling bst_child is True.

Then I added the code that finds the depth of the binary search tree. I made two different binary search trees by sorting the first list.

In this case, the first list is [4,2,1,3,6,5,7] and the second list is [1,2,3,4,5,6,7], which is sorted.

The depth of binary search tree built from the first list is 2, while the one built from the sorted list is 6.

unsorted = [4,2,1,3,6,5,7]
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(t1)
print(t2)
print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

Output is (after pretty printing the nested lists):

[4, 
  [2, 
    [1, None, None], 
    [3, None, None]
  ], 
  [6, 
    [5, None, None],
    [7, None, None]]
  ]
]

[1, None, 
  [2, None, 
    [3, None,
      [4, None,
        [5, None,
          [6, None,
            [7, None, None]
          ]
        ]
      ]
    ]
  ]
]

True True
2 6

I thought that I made the binary search tree and the code finding depth well. But when I tried with a long list, my vscode could not print proper result.

When I tried with the list whose length is 20, it worked.

unsorted = list(np.random.randint(0,1000,20))
sorted = unsorted.copy()
sorted.sort()

t1 = bst_build(unsorted)
t2 = bst_build(sorted)

print(bst_check(t1), bst_check(t2))
print( bst_depth(t1), bst_depth(t2) )

Output:

True True
5 19

However, When the length of list is about 30, it does not work. The length of the sorted list is 30, but the result is not 29 but some other number, such as 3, or a recursion error occurs:

maximum recursion depth exceeded while calling a Python object

So I increased the recursion limit by adding the sys.setrecursionlimit.

Then my code works until the length of list is about 40~50.

But when the length of list is over 50, this method still gets into the same issue. I also tried with sys.setrecursionlimit(1000000) or over millions, but it doesn't help.

Even sometimes nothing is printed.

How can I solve this problem?