# Java recursive solution using stack. O(h) extra memory (where "h" is the "height" of the list)

• Hey there!

The main idea is to keep only a stack of parent level states. Each state holds a list of NestedIntegers and the last iteration index.

``````public class NestedIterator implements Iterator<Integer> {
private final Stack<State> states;
private List<NestedInteger> currentList;
private int currentIndex;

public NestedIterator(List<NestedInteger> nestedList) {
currentList = nestedList;
currentIndex = -1;
states = new Stack<>();
}

@Override
public Integer next() {
return currentList.get(++currentIndex).getInteger();
}

@Override
public void remove() {
}

@Override
public boolean hasNext() {
if (moveNext(currentList, currentIndex)) {
return true;
}

if (states.size() > 0) {
State state = states.pop();
currentList = state.list;
currentIndex = state.index;
return hasNext();
}

return false;
}

private boolean moveNext(List<NestedInteger> currentList, int currentIndex) {
for (int i = currentIndex + 1; i < currentList.size(); ++i) {
NestedInteger nestedInteger = currentList.get(i);
if (nestedInteger.isInteger()) {
this.currentList = currentList;
this.currentIndex = i - 1;
return true;
}

List<NestedInteger> list = nestedInteger.getList();
if (list.isEmpty()) {
continue;
}

states.push(new State(currentList, i));
if (moveNext(list, -1)) {
return true;
}
states.pop();
}

return false;
}

private static class State {
private final List<NestedInteger> list;
private final int index;

public State(List<NestedInteger> list, int index) {
this.list = list;
this.index = index;
}
}
}
``````

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