New update is available. Click here to update.

Last Updated: 25 Mar, 2021

Difficulty: Moderate

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

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

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

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

For each **‘i**’, we can track the closest node for which this ‘**i**’th node is on the right subtree using stack. After this, we just need to check whether the value of ‘**i’**th node i.e **ARR[i] **is greater or smaller than this root value.

**Algorithm**

- Create an empty stack.
- Initialize an integer variable
**‘ROOT’:= 0.** - Run a loop where
**‘i’**ranges from 0 to**‘N’**- 1 and for each**‘i’**do the following -:- If
**‘ARR[i]’ < ‘ROOT’,**then return False. - Keep removing elements from the stack while
**ARR[i]**is greater than the stack top and the stack is not empty. Assign the last removed element to**‘ROOT’.**If no element is removed, then**‘ROOT’**will not change. - Push
**‘ARR[i]’**in the stack.

- If
- Return True.

We can implement the previous approach without using the stack as follow -:

**Algorithm**

- Initialize two integer variables
**‘ROOT ’:= 0**and a pointer ‘**P’:= -1.** - Run a loop where ‘i’ ranges from 0 to ‘N’-1 and for each ‘i’ do the following -:
- If
**‘ARR[i]’ < ‘ROOT’,**then return False. - Run a while loop till
**‘P’ >= 0**and**‘ARR[i]’ > ‘ARR[P]’,**and in each iteration do**‘ROOT’:= ‘ARR[P]’**and decrement**‘P’**by 1. - Increment
**‘P’**by 1 and do**ARR[P]:= ARR[i].**

- If
- Return True.

SIMILAR PROBLEMS

Hills and Soldier

Posted: 7 Jul, 2022

Difficulty: Moderate

Hills and Soldier

Posted: 7 Jul, 2022

Difficulty: Moderate

Next Greater Element II

Posted: 9 Sep, 2022

Difficulty: Moderate

Equal Arrays

Posted: 29 Sep, 2022

Difficulty: Moderate

Three Sum

Posted: 24 Nov, 2022

Difficulty: Moderate

Sort 0s, 1s, 2s

Posted: 24 Dec, 2022

Difficulty: Easy

Popular Interview Problems: