# 255. Verify Preorder Sequence in Binary Search Tree

Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

You may assume each number in the sequence is unique.

Could you do it using only constant space complexity?

Thoughts

1. keep track of prev val in order to compare whether there is a new right branch
2. keep track of lower bound value of parent node for branching to the right

Code: space complexity of O(n)

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN;
stack<int> nodes;

for(auto p : preorder){
if(p < low) return false;
while(!nodes.empty() && p > nodes.top()){
// find the new lower bound
low = nodes.top(); nodes.pop();
}

// new reference
nodes.push(p);
}
return true;
}
};
``````

Code: space complexity of O(n) Python

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

return True
``````

Code: Use two stack (Java)

``````class Solution {
public boolean verifyPreorder(int[] preorder) {
Stack<Integer> stack = new Stack<>();
Stack<Integer> inOrder = new Stack<>();

for(int val : preorder){
if(!inOrder.isEmpty() && val < inOrder.peek()) return false;
while(!stack.isEmpty() && val > stack.peek()){
// new traced parent node
inOrder.push(stack.pop());
}
stack.push(val);
}
return true;
}
}
``````

Code: space complexity of O(1): MUST USE POINTER!

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN, branch_i = -1;
for(auto val : preorder){
if(val < low) return false;
// trace back to the parent node on which cur node based to the right
while(branch_i >= 0 && val > preorder[branch_i]){
low = preorder[branch_i--];
}
// update new branch compare value
preorder[++branch_i] = val;
}
return true;
}
};
``````

Special Thanks stefanpochmann for the reference