Sponsored
Sponsored
The recursive approach leverages the call stack to manage the traversal of the multi-dimensional array. This approach requires defining a function that will be called recursively whenever an array is encountered.
When implementing this recursively, we check if the element is an integer; if so, we yield it. If it is an array, we recursively call the function on this array.
Time Complexity: O(N), where N is the total number of integers in the arrays since we visit each element once.
Space Complexity: O(D) in the worst case due to recursion, where D is the depth of the nested lists.
1def inorderTraversal(arr):
2
The function inorderTraversal takes a multi-dimensional array arr and iterates over its elements. If an element is an integer, it's directly yielded. If it is a list, the function is called recursively on the sublist, using yield from to yield each item from the resulting generator.
This method uses a stack to keep track of the state of the array traversal. It mimics the behavior of the call stack in recursion but uses an explicit data structure. We push elements onto the stack in reverse order, and pop them to yield integers or explore more sub-arrays.
Time Complexity: O(N), where N is the total number of integers in the arrays.
Space Complexity: O(N) due to the use of the stack.
1function* inorderTraversal(arr) {
2 const stack = [...arr].reverse();
3 while (stack.length) {
4 const item = stack.pop();
5 if (typeof item === 'number') {
6 yield item;
7 } else if (Array.isArray(item)) {
8 stack.push(...item.reverse());
9 }
10 }
11}
12
13// Usage example:
14const arr = [[[6]], [1, 3], []];
15const generator = inorderTraversal(arr);
16console.log([...generator]);The function creates a stack initialized with the main array in reverse. During the iteration, elements are popped from the stack: integers are yielded, and arrays are expanded (in reversed order) back into the stack, preserving the intended order of traversal.