# Why this results in StackOverflowError?

• ``````public class Solution {
private int maxNode = -1;
private int maxDist = 0;
private int[] h1;
private int[] h2;
private int[] prevDep;
private int[] suc;

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
List<Integer> res = new ArrayList<>();
h1 = new int[n];
h2 = new int[n];
prevDep = new int[n];
suc = new int[n];

if (edges == null || edges.length == 0) {
if (n == 1) {
}

return res;
}

int i, j;
int cur;
int cnt;

for (int[] e : edges) {
i = e[0];
j = e[1];

}

}

}

dfs(0);

cur = maxNode;
cnt = h2[maxNode];

while (cnt != (maxDist - 1) / 2) {
cur = suc[cur];
cnt++;
}

if (maxDist % 2 == 0) {
}

return res;
}

private void dfs(int n) {
h1[n] = prevDep[n];

for (int next : adj[n]) {

prevDep[next] = prevDep[n] + 1;
suc[next] = n;

dfs(next);

int tmpDep = h1[next] == prevDep[next] ? h2[next] + 1 : h1[next] + 1;

if (tmpDep > h1[n]) {
h2[n] = h1[n];
h1[n] = tmpDep;
suc[n] = next;
}
else if (tmpDep > h2[n]) {
h2[n] = tmpDep;
}
}

if (h1[n] + h2[n] + 1 > maxDist) {
maxDist = h1[n] + h2[n] + 1;
maxNode = n;
}
}
}
``````

I've tried my best to remove the number of parameters passed into the dfs() method. But it still results in StackOverflowError. But I've seen similar solution that's accepted. Can anyone help? Thx!

• After several attempts, I somewhat figure out the reason. If you change the type of your adj from `ArrayList` to (say) `HashSet`, your code simply passes through.

In fact, the remove operation of `ArrayList` runs in linear worst time, not O(1) time, which may result in an O(n2) solution. But I am not quite sure why it causes the StackOverflowException, and in fact, your code does not trigger the exception in my local machine for the same test case.

• Thank you so much for the reply. Nice catch! Didn't think much about the O(n) complexity of the remove operation. I used it to avoid passing in the parent. Still SOF after changing to HashSet.

• Solved after using a boolean array visited.. So the stack is just one call away from overflow?.. Interesting

• I guess it might be because the Stack Limit set by Leetcode is relatively small, and for this particular problem, the memory occupied is just above or below the threshold, which makes the behavior really subtle. In fact, I changed `ArrayList` to `HashSet` and got accepted. Anyway, I guess it is more important to know how the solution works. :-P

• Agree. Thank you!

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