Binary Search TreesProblem 19 of 22
Check preorder is valid or not
Problem Statement
Given a preorder traversal of a BST, check if it represents a valid BST. A valid preorder sequence should be able to construct a valid BST.
Example:
Valid Preorder: [40, 30, 35, 80, 100]
Can construct:
40
/ \
30 80
\ \
35 100
Output: true
Invalid Preorder: [40, 30, 35, 20, 80, 100]
After 35, we go to right subtree of 30 (35 > 30)
But 20 < 30, cannot go back to left subtree
Output: false
Approach 1: Brute Force (Try to Construct BST)
Intuition
Actually try to construct a BST from the preorder. If construction succeeds without violation, it's valid.
Algorithm
- Use recursive approach with range bounds
- First element is root
- Elements smaller than root go to left subtree
- Elements larger than root go to right subtree
- If any element violates range, return false
java
public class Solution {
private int idx = 0;
private boolean constructBST(int[] preorder, long minVal, long maxVal) {
if (idx >= preorder.length) return true;
int val = preorder[idx];
if (val < minVal || val > maxVal) {
return true;
}
idx++;
boolean left = constructBST(preorder, minVal, val - 1);
boolean right = constructBST(preorder, val + 1, maxVal);
return left && right;
}
public boolean isValidPreorderBruteForce(int[] preorder) {
if (preorder.length == 0) return true;
idx = 0;
constructBST(preorder, Long.MIN_VALUE, Long.MAX_VALUE);
return idx == preorder.length;
}
}Complexity Analysis
- Time Complexity: O(n) - Each element processed once
- Space Complexity: O(n) - Recursion stack
Approach 2: Optimal (Using Stack with Lower Bound)
Intuition
Use a stack to simulate the construction process. Maintain a lower bound that represents the minimum valid value. If we encounter a value less than the lower bound, the sequence is invalid.
Algorithm
- Initialize lower bound as negative infinity
- Use stack to track ancestors
- For each element:
- If less than lower bound, invalid
- Pop elements smaller than current (moving to right subtree)
- Update lower bound to last popped value
- Push current element
- If all elements processed successfully, valid
java
import java.util.*;
public class Solution {
public boolean isValidPreorder(int[] preorder) {
Stack<Integer> stack = new Stack<>();
int lowerBound = Integer.MIN_VALUE;
for (int val : preorder) {
// If current value is less than lower bound, invalid
if (val < lowerBound) {
return false;
}
// Pop all elements smaller than current
while (!stack.isEmpty() && stack.peek() < val) {
lowerBound = stack.pop();
}
// Push current value
stack.push(val);
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n) - Each element pushed and popped at most once
- Space Complexity: O(n) - Stack space
Approach 3: Space Optimized (Using Array as Stack)
Intuition
Use the input array itself as a stack to achieve O(1) extra space.
Algorithm
- Use a variable to track stack top position
- Reuse input array for stack operations
- Same logic as stack approach
java
public class Solution {
public boolean isValidPreorderO1Space(int[] preorder) {
int lowerBound = Integer.MIN_VALUE;
int stackTop = -1;
for (int val : preorder) {
if (val < lowerBound) {
return false;
}
while (stackTop >= 0 && preorder[stackTop] < val) {
lowerBound = preorder[stackTop];
stackTop--;
}
stackTop++;
preorder[stackTop] = val;
}
return true;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1) - Modifies input array
Approach 4: Recursive with Range Check
Intuition
Similar to validating BST with range check but applied to preorder sequence.
java
public class Solution {
private int idx = 0;
private boolean validate(int[] preorder, long minVal, long maxVal) {
if (idx >= preorder.length) {
return true;
}
int root = preorder[idx];
if (root < minVal || root > maxVal) {
return true;
}
idx++;
return validate(preorder, minVal, root) &&
validate(preorder, root, maxVal);
}
public boolean isValidPreorderRecursive(int[] preorder) {
idx = 0;
validate(preorder, Long.MIN_VALUE, Long.MAX_VALUE);
return idx == preorder.length;
}
}Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n) - Recursion stack
Key Takeaways
- Preorder property: Root comes first, then left subtree, then right subtree
- Lower bound concept: Once we move to right subtree, we can't go back
- Stack simulation: Simulates the recursive construction process
- Key insight: If a smaller value appears after moving to right subtree, invalid
- This is LeetCode #255 - Verify Preorder Sequence in BST
- Similar concept applies to validating postorder sequence
- The stack approach is elegant and intuitive once understood