Trick: Lazy Expansion of a Multiway Tree

Today, we will discuss a highly insightful design problem. Why is it insightful? We'll explain later.

1. Problem Description

This is LeetCode's Problem 341 "Flatten Nested List Iterator":

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Our algorithm will be input with a list of NestedInteger. Our task is to write an iterator class NestedIterator to "flatten" this list with nested NestedInteger structure:

public class NestedIterator implements Iterator<Integer> {
    // The constructor takes a list of NestedInteger as input
    public NestedIterator(List<NestedInteger> nestedList) {}
    
    // Return the next integer
    public Integer next() {}

    // Is there a next element?
    public boolean hasNext() {}
}

class NestedIterator: public Iterator<int> {
public:
    // Constructor takes a list of NestedInteger
    NestedIterator(vector<NestedInteger> &nestedList) {}
    
    // Return the next integer
    int next() {}

    // Does it have the next element?
    bool hasNext() {}
};

class NestedIterator:
    def __init__(self, nestedList: List[NestedInteger]):
        # The constructor takes a list of NestedInteger
        pass

    # Return the next integer
    def next(self) -> int:
        pass

    # Is there a next element?
    def hasNext(self) -> bool:
        pass

type NestedIterator struct{}

// The constructor takes a list of NestedInteger as input
func Constructor(nestedList []*NestedInteger) *NestedIterator {}

// Return the next integer
func (iter *NestedIterator) Next() int {}

// Is there a next element?
func (iter *NestedIterator) HasNext() bool {}

var NestedIterator = function(nestedList) {
    // The constructor takes a list of NestedInteger as input
}

// Return the next integer
NestedIterator.prototype.next = function() {}

// Is there a next element?
NestedIterator.prototype.hasNext = function() {}

The NestedIterator class we write will be used as follows, first call the hasNext method, then call the next method:

NestedIterator i = new NestedIterator(nestedList);
while (i.hasNext())
    print(i.next());

Those familiar with design patterns would know that an iterator is a type of design pattern, aiming to shield the caller from the underlying data structure's details, allowing simple ordered traversal through the hasNext and next methods.

Why is this problem considered insightful? Because I've recently been using a software similar to Evernote called Notion (quite popular). One of the highlights of this software is that "everything is a block," such as titles, pages, and tables being blocks. Some blocks can even be nested infinitely, breaking the traditional notebook structure of "Folder" -> "Notebook" -> "Note."

Reflecting on this algorithm problem, the NestedInteger structure is also a type that supports infinite nesting and can represent both integers and lists simultaneously. I imagine Notion's core data structure, block, is likely designed similarly.

So, back to our algorithm problem, how do we solve it? The NestedInteger structure can be infinitely nested. How do we "flatten" this structure, shield the caller of the iterator from the underlying details, and achieve a flattened output?

2. Solution Approach

3. Advanced Idea