Verify Preorder Sequence in Binary Search Tree

Posted on |

Two solutions for leetcode 255.

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.

The preorder of binary serch tree has a rules that if you go left it means that the sequence is descendant,as the sequence became ascendant it start to go the right subtree. Those numbers that before the changing points could be used to restrict the limits of right subtrees. We need to memo the minimum value in the tree that we already traversed , using a stack to track the nodes of the tree and pop out the nodes that is smaller than the min value we set and update the current min.

first solution using stack

time: O(N) space: O(N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        stack<int> st;
        int min_v = numeric_limits<int>::min();
        for(auto& num : preorder){
            if (num < min_v) return false;
            while(!st.empty() && st.top() < num){
                min_v = st.top();
                st.pop();
            }
            st.push(num);
        }
        return true;
    }
};

second solution (inplace)

time : O(N) space : O(1)
we found that we don’t have to use extra space since the stack size will never biger than the orgin one. Modified the origin vector to perform like a stack. Used a variable i to track the stack and act like a pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int i = -1, min_v = numeric_limits<int>::min();
        for(auto& num : preorder){
            if (num < min_v) return false;
            while(i >= 0 && preorder[i] < num){
                min_v = preorder[i--];
            }
            preorder[++i] = num;
        }
        return true;
    }
};