Check If Preorder Traversal Is Valid

Moderate
0/80
Average time to solve is 35m
profile
Contributed by
15 upvotes
Asked in companies
AdobeVMware IncCadence Design Systems

Problem statement

You are given an array 'ARR' of positive integers. Your task is to check whether the array 'ARR' is a valid Preorder Traversal of a Binary Search Tree.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a value greater than or equal all the values in the node's left subtree and less than those in its right subtree.

For Example 
Consider the array ARR = [ 7, 4, 8 ] having 3 elements. 
This array represents the pre-order traversal of the below tree.

bst

Hence, the above array 'ARR' is a valid Preorder Traversal of a Binary Search Tree.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains an integer 'N', denoting the number of elements in the array 'ARR'.

The second line of each test case contains 'N' space-separated integers denoting the array elements.
Output Format 
For each test case, print 1 if the array represents a valid preorder traversal of a Binary Search Tree. Otherwise, print 0.

Print the output of each test case in a new line.
Note 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 10
1 <= N <= 10^5
0 <= ARR[i]  <= 10^9

Time Limit: 1 sec
Sample Input 1
2
7
4 2 1 3 6 5 7
4
5 4 6 4
Sample Output 1
1
0
Explanation for Sample Input 1
For the first test case : 
Consider the below Binary Search Tree

bst_example 

Its preorder traversal is [ 4, 2, 1, 3, 6, 5, 7 ] which is equal to the input array 'ARR'. 
Therefore, the answer is 1 in this case.

For the second test case : 
It can be seen that for the array ARR = [ 5, 4, 6, 4 ], there does not exist a Binary Search Tree for which the above array can represent its pre-order traversal.
Sample Input 2
2
3
6 2 6
4
5 6 1 4
Sample Output 2
1
0
Hint

Try to think of a recursive approach to divide the array into left subtree and right subtree and check for them independently.

Approaches (2)
Recursive Approach

The idea is to find the first node in the array having a value greater than the array's first element, i.e., its root. Let ARR[i] be that element. Then we will treat the elements to the right of ARR[i], including ARR[i] itself as the right subtree and all the elements before ARR[i] as the left subtree. 

 

Now we will recursively check whether the right subtree and left subtree represent a valid Preorder traversal of a Binary Search Tree independently. We will also maintain two variables, upperBound and lowerBound, to denote the maximum possible and minimum possible that a node can contain. We will initialize the lowerBound as INT_MIN and upperBound as INT_MAX. Whenever we visit a left subtree, we will update the upperBound to the data contained on the root of the tree, and lowerBound will remain unchanged, and whenever we visit a right subtree we will update the lowerBound to the data contained on the root of the tree and upperBound will remain unchanged. 

 

Algorithm

 

  • It takes the input array ARR, two indices i and j denoting the subarray ARR[i],ARR[i+1]….ARR[j], and two variables, upperBound and lowerBound, as its parameters.
  • If i is equal to j, then we will return 1 if ARR [i] lies between lowerBound and upperBound otherwise, we will return 0.
  • Initialize a variable firstGreaterIndex as j + 1 to store the index of the first position containing a greater value than the current node.
  • Iterate through k = i + 1 to j 
    • If ARR[k] does not lie between lowerBound and upperBound, then we will return 0 and end our recursive function here.
    • If ARR[k] is greater than ARR[i], then set firstGreaterIndex as k and break the loop.
  • If firstGreaterIndex is not equal to i + 1 then we will recursively call for the left subtree taking i = i + 1 and j = firstGreaterIndex - 1 and the updated upperBound as ARR [i] . We will return 0 if the recursive call returns 0.
  • If firstGreaterIndex is not equal to j + 1 then we will recursively call for the right subtree taking  i = firstGreaterIndex and j = j and the updated lowerBound as ARR [i] . We will return 0 if the recursive call returns 0.
  • We will return 1 if we have not returned any value till now.
  • Now in our main function we will call the recursive function taking the input array ARR and the following parameters i = 0, j = N-1, upperBound = INT_MAX, lowerBound = INT_MIN and return its output.
Time Complexity

O(N^2), where ‘N’ is the number of elements in the array. 

 

In the worst case, when the array is sorted in decreasing order, there will be N recursive calls, and each recursive call takes O(N) time to find the firstGreaterIndex variable. Hence, the overall time complexity will be O(N^2).

Space Complexity

O(N), where ‘N’ is the number of elements in the array. 

 

In the worst case, when the array is sorted in decreasing order, there will be N recursive calls, and the corresponding recursion depth will be N. Hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Check If Preorder Traversal Is Valid
Full screen
Console