bst_bfs.py

importcollections

defbst_bfs(A):

N=len(A)
interval=collections.deque([(float('-inf'), A[0]), (A[0], float('inf'))])

foriinrange(1, N):
whileinterval:
lower, upper=interval.popleft()
iflower<A[i] <upper:
interval.append((lower, A[i]))
interval.append((A[i], upper))
break

ifnotinterval:
returnFalse

returnTrue

if__name__=="__main__":
A= [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 12]
print(bst_bfs(A))
A= [10, 8, 11, 1, 9, 0, 5, 3, 6, 4, 7]
print(bst_bfs(A))