Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Verify Preorder Sequence in Binary Search Tree

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
11 upvotes
Asked in companies
AmazonNewgen Software

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.

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.
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
Full screen
Console