4Lines Reference

https://leetcode.com/discuss/51543/java-o-n-and-o-1-extra-space

```
public boolean verifyPreorder(int[] pre) {
int i, j, n = pre.length, minBd = Integer.MIN_VALUE;
for (i = 1, j = 0; i < n && pre[i] > minBd; pre[++j] = pre[i++])
for (; j >= 0 && pre[j] < pre[i]; minBd = pre[j--]);
return i >= n;
}
```

Anther O(1) space solution without abusing the given array:

Each time when you encounter a preorder[i] > preorder[i - 1], you know you are going to right branch, and you need to update the min boundary for that right sub tree. The min boundary is the local parent of that right sub tree, the value is indeed equals to the largest preorder element among [0 ~ i - 1] while smaller than preorder[i].

```
public class Solution {
public boolean verifyPreorder(int[] preorder) {
int min = Integer.MIN_VALUE, n = preorder.length, j, i, k;
for (i = 1; i < n && preorder[i] > min; i++)
if (preorder[i - 1] < preorder[i]) {
for (k = i - 1, j = i - 2; j >= 0; j--)
if (preorder[j] < preorder[i] && preorder[j] > preorder[k]) k = j;
min = preorder[k];
}
return i >= n;
}
}
```