New update is available. Click here to update.

Verify Preorder Sequence in Binary Search Tree

Posted: 25 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.

alt text

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.
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of a single integer ‘N’ representing the size of the list/array ‘ARR’.

The second line of each test case consists of ‘N’ single space-separated integers representing list/ array ‘ARR’.
Output format :
For each test case, print a single line containing a string ‘True’ if  ‘ARR’ can represent Preorder Traversal of a Binary Search Tree, otherwise print ‘False’.  

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
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.