• Time:O(n)
• Space:O(h)

C++

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int i = 0;
dfs(preorder, i, INT_MIN, INT_MAX);
return i == preorder.size();
}

private:
void dfs(const vector<int>& preorder, int& i, int min, int max) {
if (i == preorder.size())
return;
if (preorder[i] < min || preorder[i] > max)
return;

const int val = preorder[i++];
dfs(preorder, i, min, val);
dfs(preorder, i, val, max);
}
};
``````

JAVA

``````class Solution {
public boolean verifyPreorder(int[] preorder) {
dfs(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
return i == preorder.length;
}

private int i = 0;

private void dfs(int[] preorder, int min, int max) {
if (i == preorder.length)
return;
if (preorder[i] < min || preorder[i] > max)
return;

final int val = preorder[i++];
dfs(preorder, min, val);
dfs(preorder, val, max);
}
}
``````

Python

``````class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
i = 0

def dfs(min: int, max: int) -> None:
nonlocal i
if i == len(preorder):
return
if preorder[i] < min or preorder[i] > max:
return

val = preorder[i]
i += 1
dfs(min, val)
dfs(val, max)

dfs(-math.inf, math.inf)
return i == len(preorder)
``````

• Time:O(n)
• Space:O(n)

C++

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN;
stack<int> stack;

for (const int p : preorder) {
if (p < low)
return false;
while (!stack.empty() && stack.top() < p)
low = stack.top(), stack.pop();
stack.push(p);
}

return true;
}
};
``````

JAVA

``````class Solution {
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE;
Deque<Integer> stack = new ArrayDeque<>();

for (final int p : preorder) {
if (p < low)
return false;
while (!stack.isEmpty() && stack.peek() < p)
low = stack.pop();
stack.push(p);
}

return true;
}
}
``````

Python

``````class Solution:
def verifyPreorder(self, preorder: List[int]) -> List[int]:
low = -math.inf
stack = []

for p in preorder:
if p < low:
return False
while stack and stack[-1] < p:
low = stack.pop()
stack.append(p)

return True
``````

• Time:O(n)
• Space:O(1)

C++

``````class Solution {
public:
bool verifyPreorder(vector<int>& preorder) {
int low = INT_MIN;
int i = -1;

for (const int p : preorder) {
if (p < low)
return false;
while (i >= 0 && preorder[i] < p)
low = preorder[i--];
preorder[++i] = p;
}

return true;
}
};
``````

JAVA

``````class Solution {
public boolean verifyPreorder(int[] preorder) {
int low = Integer.MIN_VALUE;
int i = -1;

for (final int p : preorder) {
if (p < low)
return false;
while (i >= 0 && preorder[i] < p)
low = preorder[i--];
preorder[++i] = p;
}

return true;
}
}
``````

Python

``````class Solution:
def verifyPreorder(self, preorder: List[int]) -> bool:
low = -math.inf
i = -1

for p in preorder:
if p < low:
return False
while i >= 0 and preorder[i] < p:
low = preorder[i]
i -= 1
i += 1
preorder[i] = p

return True
``````