Check Preorder of BST

Problem Overview

In BST preorder you go root → left → right.

Intuition

In BST preorder you go root → left → right. Once you leave a subtree for a right child, every later value must stay above that subtree’s root (the new lower bound). A decreasing stack of ancestors plus that lower bound detects any value that would illegally re-enter a finished left region.

Algorithm

1Initialize an empty stack and last = −∞ (lower bound for the next node).
2For each ele in the candidate preorder:
3 • While the stack top is < ele, pop it and set last to the popped value (leaving a left subtree).
4 • If ele < last, return false — value sits below the allowed lower bound.
5 • Push ele onto the stack.
6If the scan finishes without violations, return true.

Example Walkthrough

Input: arr = [40, 30, 35, 80, 100]

1. Push 40, then 30 (left of 40).
2. 35 > 30: pop 30, last = 30; push 35 (right of 30, still left of 40).
3. 80 > 35: pop 35 then 40, last = 40; push 80 (right of 40).
4. 100 > 80: pop 80, last = 80; push 100. No value fell below last → true.

Output: true

Common Pitfalls

• Update the lower bound only when popping smaller ancestors — that is when you move to a right subtree.
• A value smaller than last after those pops always means an invalid preorder.
• This assumes distinct keys (standard for this GFG statement).
• Empty or single-element arrays are valid BSTs.

Check Preorder of BST.java

Java


import java.util.*;

class Solution {

    // Approach: Simulate BST preorder with a decreasing stack. last is the
    // lower bound after finishing a left subtree (moving to a right child).
    // Pop while the top is smaller than the next value and update last; if the
    // next value is then still below last, the sequence cannot be a BST preorder.
    // Complexity: O(n) time and O(n) space.
    public boolean canRepresentBST(List<Integer> arr) {
        Stack<Integer> st = new Stack<>();
        int last = Integer.MIN_VALUE;
        for (int ele : arr) {
            while (!st.isEmpty() && st.peek() < ele) {
                last = st.pop();
            }
            if (last > ele) {
                return false;
            }
            st.push(ele);
        }
        return true;
    }
}

Was this solution helpful?