# Recursive solution, and iterative solution translated from the recursive solution

• My recursive solution leads to stack overflow. So I translated the recursive solution to iterative solution by following some mechanical steps. Then the stack overflow problem is solved. Maybe the next step is translating the iterative solution to a more semantically reasonable solution such that nobody can tell it is translated mechanically from recursive solution..

Recursive solution:

``````public class Solution {
private int[] preorder;

private int verifyPreorder(int index, Integer low, Integer high) {
if (index == preorder.length) {
return index;
}
int curNum = preorder[index];
if ((low == null || low < curNum) && (high == null || curNum < high)) {
int leftCallIndexRet = verifyPreorder(index + 1, low, curNum);
return verifyPreorder(leftCallIndexRet, curNum, high);
} else {
return index;
}
}

public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return true;
}
this.preorder = preorder;
return verifyPreorder(0, null, null) == preorder.length;
}
}
``````

Iterative solution translated from the above recursive solution:

``````public class Solution {
private int[] preorder;

private int verifyPreorder() {
class Frame {
int index;
Integer low;
Integer high;
boolean leftCall;
Frame(int index, Integer low, Integer high, boolean leftCall) {
this.index = index;
this.low = low;
this.high = high;
this.leftCall = leftCall;
}
Integer ret;
}
Stack<Frame> stack = new Stack<>();
stack.push(new Frame(0, null, null, false));

do {
if (stack.peek().ret == null) {
int index = stack.peek().index;
Integer low = stack.peek().low;
Integer high = stack.peek().high;

if (index == preorder.length) {
stack.peek().ret = index;
} else {
int curNum = preorder[index];
if ((low == null || low < curNum) && (high == null || curNum < high)) {
stack.push(new Frame(-1, curNum, high, false));
stack.push(new Frame(index + 1, low, curNum, true));
} else {
stack.peek().ret = index;
}
}
} else {
Frame frame = stack.pop();
int ret = frame.ret;
boolean leftCall = frame.leftCall;
if (leftCall) {
stack.peek().index = ret;
} else {
stack.peek().ret = ret;
}
}
} while (stack.size() > 1);

return stack.pop().ret;
}

public boolean verifyPreorder(int[] preorder) {
if (preorder == null || preorder.length == 0) {
return true;
}
this.preorder = preorder;
return verifyPreorder() == preorder.length;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.