# simple python O(n) Time and Space Utilizing one Stack with explanation

• ``````class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
low_bound = float("-inf")
upper_bound = float("inf")
n = len(preorder)
if n < 2:
return True
# ele (low_bound,upper_bound,value,left_visited,right_visited)
stack = []
stack.append([low_bound, upper_bound, preorder[0], False, False])
for i in xrange(1, n):
ele = preorder[i]
while len(stack) > 0:
top = stack[-1]
# the ele is the node's child only when
# the ele is within the boundary and the corresponding subtree of the node is not visited
if (not top[3] and top[0] < ele < top[2]) or (not top[4] and top[2] < ele < top[1]):
break
else:
stack.pop()
# if stack is empty which means we can't find parent for ele, so return False
if len(stack) == 0:
return False
top = stack[-1]
if not top[3] and top[0] < ele < top[2]:
stack[-1][3] = True
stack.append([top[0], top[2], ele, False, False])
else:
# if the ele is the right child of node, this means left child is None or has been visited,
# so assign the left_visited as True
stack[-1][3] = True
stack[-1][4] = True
stack.append([top[2], top[1], ele, False, False])
return True
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.