# Verify Preorder Sequence in Binary Search Tree

Moderate
0/80
Average time to solve is 30m
Contributed by

## Problem statement

You are given an array/list ‘ARR’ consisting of ‘N’ distinct integers. You need to check whether ‘ARR’ can represent the Preorder Traversal of a Binary Search Tree.

You should return true if ‘ARR’ can represent Preorder Traversal of a Binary Search Tree, otherwise return false.

Example:
``````Consider ‘ARR’ = [40, 30, 35, 80, 100]. You can see that it is the preorder traversal of the Binary Search Tree shown above.

Thus, we should return true in this case.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 50
1 <= N <= 10 ^ 4
1 <= ARR[i] <= 10 ^ 9

Where ‘ARR[i]’ is the element of the given array ‘ARR’ at index ‘i’.

Time limit: 1 sec.
``````
##### Sample Input 1:
``````2
1
1
5
40 30 35 80 100
``````
##### Sample Output 1:
``````True
True
``````
##### Explanation of Sample Input 1:
``````Test case 1:
There is only one element is ‘ARR’, and it is the preorder traversal of a Binary Search tree having a single node with value 1.

Test case 2:
See the problem statement for an explanation.
``````
##### Sample Input 2:
``````2
3
2 4 1
6
5 2 3 1 7 8
``````
##### Sample Output 2:
``````False
False
``````
Console