Problem

Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.

A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.

inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input:
arr = [[[6]],[1,3],[]]
Output:
 [6,1,3]
Explanation:
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true

Example 2:

1
2
3
4
5

Input:
arr = []
Output:
 []
Explanation: There are no integers so the generator doesn't yield anything.

Solution

Method 1 - Recursion

Here is the approach:

  • Check each element of the array.
  • If the element is an integer, yield it.
  • If the element is a list (another array), recursively apply the same process to this list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    // Helper method to recursively traverse the multi-dimensional array
    private void inorderTraversalHelper(Object[] arr, List<Integer> result) {
        for (Object element : arr) {
            if (element instanceof Integer) {
                result.add((Integer) element);
            } else {
                // The element is a nested array, so recursively apply inorder traversal
                inorderTraversalHelper((Object[]) element, result);
            }
        }
    }

    public Iterator<Integer> inorderTraversal(Object[] arr) {
        List<Integer> result = new ArrayList<>();
        inorderTraversalHelper(arr, result);
        return result.iterator();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        Object[] arr = new Object[]{1, new Object[]{2, 3}, 4, new Object[]{5, new Object[]{6, 7}}};
        Iterator<Integer> iterator = sol.inorderTraversal(arr);
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import Generator, List, Union

NestedList = List[
    Union[int, "NestedList"]
]  # A type alias for multi-dimensional arrays


class Solution:
    def inorder_traversal(self, arr: NestedList) -> Generator[int, None, None]:
        for element in arr:
            if isinstance(element, int):
                yield element
            else:
                # The element is a nested array (list), so recursively apply inorder traversal
                yield from self.inorder_traversal(element)

Complexity

  • ⏰ Time complexity: O(n), where n is the total number of elements including nested lists. Each element is processed once.
  • 🧺 Space complexity: O(d), where d is the maximum depth of the nested arrays. This represents the call stack depth for the recursion.