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.
Follow up: Could you do it using only constant space complexity?
Recursive is not O(1) space
public boolean verifyPreorder(int[] preorder) {
return Helper(preorder, 0, preorder.length - 1);
}
private boolean Helper(int [] preorder, int b, int e){
if(b >= e) return true;
else{
int root = preorder[b], i = b;
for(; i <= e; i ++){
if(preorder[i] > root)
break;
}
for(int j = i + 1; j <= e; j++)
if(preorder[j] < root){
return false;
}
return Helper(preorder, b + 1, i - 1) && Helper(preorder, i, e);
}
}