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

Problem of the day

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.

```
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

```
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.
```

```
2
1
1
5
40 30 35 80 100
```

```
True
True
```

```
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.
```

```
2
3
2 4 1
6
5 2 3 1 7 8
```

```
False
False
```