Check If Preorder Traversal Is Valid

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.

Instead of traversing the complete array again and again in the previous approach to find the value of firstGreaterIndex, we can use a stack to store the array elements. For the element at position i, the element at the position firstGreaterIndex will be the next Greater Element for the element ARR[i]. Hence we can use an approach similar to the algorithm to find the next Greater Element to solve our problem.

Algorithm

• Initialize an empty stack of integers.
• Initialize a variable lowerBound to store the value of the root of the current tree. Initialize is as INT_MIN. 
• Iterate through i = 0 to N - 1
  • If ARR[i] is smaller than lowerBound, then we will return 0. We are returning 0 here because as we are moving to the right of the input array we are updating the lowerBound variable. The lowerBound variable is monotonically increasing. Therefore we want all values on the right to have a value greater than or equal to lowerBound. Hence, we will return 0 as we found a variable not satisfying our conditions.
  • Repeatedly
    • If the stack is non-empty, then remove the element at the top of the stack if it is smaller than ARR[i] and make the removed element as the new lowerBound.  As we were able to find a greater element for an index j < i and now we want all the unvisited elements to have a value greater than the value at the top of the stack. Hence we will update the lowerBound variable.
  • Push ARR[i] to the stack. Note that the stack will always contain elements sorted in descending order.
• Return 1 if we have not returned 0 till now.