**Solution**

**Verify Preorder Sequence in Binary Search Tree** https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/

**Brute Force**

- preOrder range from lo to hi. The first element or preOrder[lo] is the root.
- The remaining sequence should be partitioned into 2 sequences. One sequence is less than root and the other is more than root. If that doesnt happen, we return False.
- We then recurse into two sequences and make sure both of them are also valid sequences.
- This is N^2 at worst and N * Lg (N) at best when we have a balanced tree.
- The python version TLE but Java version passes the cases.

```
class Solution(object):
def is_preorder(self, preorder, lo, hi):
if lo >= hi:
return True
increasing, j = False, hi+1
for i in range(lo+1, hi+1):
if not increasing and preorder[i] > preorder[lo]:
increasing, j = True, i
if increasing and preorder[i] < preorder[lo]:
return False
if increasing == False:
return self.is_preorder(preorder, lo+1, j-1)
else:
return self.is_preorder(preorder, lo+1, j-1) and self.is_preorder(preorder, j, hi)
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
return self.is_preorder(preorder, 0, len(preorder)-1)
```

**Test if every number is withing bounds**

```
class Solution(object):
def is_preorder(self, preorder, s, e, lb, ub):
if s >= e:
return True
j = e+1
r = preorder[s]
for i in range(s, e+1):
if lb <= preorder[i] <= ub:
if preorder[i] > r:
j = i
break
else:
return False
return self.is_preorder(preorder, s+1, j-1, lb, r-1) and self.is_preorder(preorder, j, e, r+1, ub)
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
return self.is_preorder(preorder, 0, len(preorder)-1, float('-inf'), float('inf'))
```

**Optimized O(N) Solution**

- Core concept: At any point, we need to figure out the lower bound for all the values yet to be seen or processed. Now how would be manage that? Visualize a BST.
- Initially that lower bound is -INF.
- You start pushing all the left most values into a stack. When you find preorder[i] > preorder[i-1], it indicates a right child. We now want to find the predecessor of this right child. The predecessor will serve as new lower bound.
- How do we find predecessor? Keep popping till you preorder[i] > st[-1].
- https://discuss.leetcode.com/topic/41210/c-easy-to-understand-solution-with-thought-process-and-detailed-explanation

```
class Solution(object):
def verifyPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: bool
"""
st = []
low = float('-inf')
for x in preorder:
if x < low:
return False
while st and st[-1] < x:
low = st.pop()
st.append(x)
return True
```