LeetCode Q255: 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?

Solution:

Use a stack to simulate the pre-order traversal. 

	class Solution {
	public:
	bool verifyPreorder(vector<int>& preorder){
	// using stack
	int sz = preorder.size();
	if(sz < 2) return true;
	stack<int> s;
	s.push(preorder[0]);
	int curr_p;
	for(int i=1; i<sz; i++){
	if(preorder[i]<s.top()){ // if current node is less than stack top, then go to left subtree
	if(preorder[i]<curr_p)
	return false;
	s.push(preorder[i]);
	}
	else{
	while(!s.empty() && s.top()<preorder[i]){ //find curr_p such that current node is right child of curr_p
	curr_p = s.top();
	s.pop();
	}
	s.push(preorder[i]);
	}
	}
	return true;
	}
	};

view raw Q255.cpp hosted with ❤ by GitHub

Also, should refer to following solutons:
1. https://leetcode.com/discuss/52060/72ms-c-solution-using-one-stack-o-n-time-and-space
2. https://leetcode.com/discuss/52744/c-o-n-log-n-recursive-solution
3. https://leetcode.com/discuss/89904/52ms-c-o-1-space-o-n-time-commented-code

Round 2 solutoin:
Tracking the upper bound and lower bound of left and right branches. To get the separate position of the branches, use binary search.

	class Solution {
	public:
	bool helper(vector<int>& preorder, int l, int r, int upper, int lower){
	if(preorder[l]>=upper||preorder[l]<=lower)
	return false;
	if(l==r)
	return true;
	int i;
	int p0=l+1, p1=r+1;
	while(p0<=p1&&p0<r+1){
	i = (p0+p1)/2;
	if(preorder[i]>=preorder[l]&&preorder[i-1]<=preorder[l])
	break;
	if(preorder[l]>preorder[i])
	p0=i+1;
	if(preorder[l]<preorder[i])
	p1=i-1;
	}
	i = (p0+p1)/2;
	bool left=true, right=true;
	if(i!=l+1)
	left = helper(preorder, l+1, i-1, preorder[l], lower);
	if(i<=r)
	right = helper(preorder, i, r, upper, preorder[l]);
	return left&&right;
	}
	bool verifyPreorder(vector<int>& preorder) {
	bool res=true;
	if(preorder.empty())
	return res;
	res=helper(preorder, 0, preorder.size()-1, INT_MAX, INT_MIN);
	return res;
	}
	};

view raw Q255Rnd2.cpp hosted with ❤ by GitHub