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.

Follow up: 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