Preorder Traversal and BST

Given an array arr[ ] of size N consisting of distinct integers, write a program that returns 1 if given array can represent preorder traversal of a possible BST, else returns 0.

Example 1:

Input:
N = 3
arr = {2, 4, 3}
Output: 1
Explaination: Given arr[] can represent
preorder traversal of following BST:
               2
                \
                 4
                /
               3

Example 2:

Input:
N = 3
Arr = {2, 4, 1}
Output: 0
Explaination: Given arr[] cannot represent
preorder traversal of a BST.

Your Task:
You don’t need to read input or print anything. Your task is to complete the function canRepresentBST() which takes the array arr[] and its size N as input parameters and returns 1 if given array can represent preorder traversal of a BST, else returns 0.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Constraints:
1 ≤ N ≤ 105
0 ≤ arr[i] ≤ 105

class Solution {
    static int canRepresentBST(int preorder[], int n) {
        // code here
         Stack<Integer> stack = new Stack<>();
        int root = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {
            if (preorder[i] < root) {
                return 0;
            }

            while (!stack.empty() && stack.peek() < preorder[i]) {
                root = stack.peek();
                stack.pop();
            }
            stack.push(preorder[i]);
        }
        return 1;
    }
}

we use a stack to keep track of the potential roots of subtrees. We initialize the root variable with the minimum integer value. Then, we iterate through the preorder array. If we find an element smaller than the root, we return 0, as it violates the BST property. Otherwise, we update the root and push the current element onto the stack. Finally, if no violation is found, we return 1.

Dryrun

Let’s do a dry run of the given example to understand how the algorithm works.

Input:
N = 3
arr = {2, 4, 3}

We initialize an empty stack and set root to Integer.MIN_VALUE.

For the first element 2:

Since the stack is empty and 2 is greater than root, we push 2 onto the stack.

For the second element 4:

Since 4 is greater than root (which is 2), we update root to 2 and pop 2 from the stack.
Now the stack is empty, and 4 is pushed onto the stack.

For the third element 3:

Since 3 is greater than the current root (which is 2), we update root to 4 and pop 4 from the stack.
Now the stack contains the element 3.

At the end, the stack is not empty, and the elements are valid according to the BST property. Therefore, the function returns 1.

Input:
N = 3
arr = {2, 4, 1}

We initialize an empty stack and set root to Integer.MIN_VALUE.

For the first element 2:

Since the stack is empty and 2 is greater than root, we push 2 onto the stack.

For the second element 4:

Since 4 is greater than root (which is 2), we update root to 2 and pop 2 from the stack.
Now the stack is empty, and 4 is pushed onto the stack.

For the third element 1:

Since 1 is less than the current root (which is 4), it violates the BST property, and we return 0.

As 1 violates the BST property, the function returns 0.