Binary Search Trees: Check If Preorder Traversal Is Valid BST

Problem Statement:

You are given a array, you need to check if array can be represented as pre-order of BST.

BST is a tree that satisfies below condition:

1. Left subtree will have the node less than the node key

2. Right subtree will have the node greater than the node key

3. Duplicate values are not allowed

Pre Order Traversal = root -> left -> right

Example:

Input: arr = [3, 2, 1, 4]

Output: yes

Solution 1: Using Stack

We will use stack to solve the problem.

Initialize a stack and minVal with INT_MIN.

Iterate through out the stack and check if the element is less than minVal, then return false.

If the stack is not empty and top of the stack is less than the current element, pop the element and update the minVal to the popped element.

Push current element into the stack.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

bool solution(vector<int> &pre)
{
    stack<int> s;
    int minValue = -1;
    for (int i = 0; i < pre.size(); i++)
    {
        if (pre[i] < minValue)
            return false;
            
        while (!s.empty() && s.top() < pre[i])
        {
            minValue = s.top();
            s.pop();
        }
        s.push(pre[i]);
    }
    return true;
}
int main()
{
    vector<int> pre = {40, 30, 35, 80, 100};
    if (solution(pre))
        cout << "true\n";
    else
        cout << "false\n";
}

Output

true