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?
CodePudding user response：
The recursion depth should not be that great on the condition that your binary tree is relatively balanced. Still, even when your binary tree is degenerate, like is what happens when you create it from a sorted sequence (sorted) then you should still only need O(n) stack space.
But your code for both bst_build and find_depth needs a lot more stack space. This is because they don't backtrack when reaching a leaf. Instead they both restart a traversal from the root, without getting out of the current recursion tree first:
bst_builddoes this by callingbst_buildagain when it wants to insert the next input fromseq. This should happen in a loop (outside of recursion), not when you are already deep in a recursion tree.find_depthdoes this by callingfind_depthagain when it reaches a leaf. This should happen by first backtracking one step and then recurring again into a sibling node. Instead it restarts the search from the root (which is a waste of time), and does so without getting out of recursion first.
This makes this code need a tremendous amount of stack space, which will be like O(n²) in the worst (degenerate) case.
Not related to your question, but it is a pity -- and completely unnecessary -- that find_depth destroys the tree as it is being traversed.
Another problem that is not related to your question: your bst_check is not correct. It will return True for the following tree:
2
/
1
\
3
Yet, this tree is not a valid BST. The requirement for a valid BST is not only that a left child is less than its parent, but that all nodes in the left subtree are less than that parent.
Here is a fix for all these issues:
def bst_build(seq):
if not seq:
return None
def add_child(main, value):
if value == main[0]:
return
childindex = 1 if main[0] > value else 2
if not main[childindex]:
main[childindex] = [value, None, None]
else:
add_child(main[childindex], value)
binary_search_tree = [seq[0], None, None]
for value in seq[1:]:
add_child(binary_search_tree, value)
return binary_search_tree
def bst_depth(b):
return 1 max(bst_depth(b[1]) if b[1] else -1, bst_depth(b[2]) if b[2] else -1)
def bst_check(b, low=float("-inf"), high=float("inf")):
return not b or (low <= b[0] <= high and bst_check(b[1], low, b[0])
and bst_check(b[2], b[0], high))