Leetcode 255 Solution

This article provides solution to leetcode question 255 (verify-preorder-sequence-in-binary-search-tree)
Categories:
Tags:
Access this page by simply typing in "lcs 255" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree

Solution

class Solution {
public:
    bool verifyPreorder(vector<int>& preorder) {
        int low = INT_MIN;
        int top = -1;

        for (auto a : preorder)
        {
            if (a <= low)
                return false;

            while (top >= 0 && a > preorder[top])
            {
                low = preorder[top];
                top--;
            }

            preorder[++top] = a;
        }

        return true;
    }
};