"Inorder" DFS Traversal (ft. Generators)
Intuition\nThe nested structure of the array suggests a recursive, tree-like structure. Thinking about how the array is flattened in this structure leads to the
# Intuition\nThe nested structure of the array suggests a recursive, tree-like structure. Thinking about how the array is flattened in this structure leads to the idea of a DFS traversal.\n\n# Approach\nFor some array, we scan the elements left to right.\n\nIf the element is a number, we add it to our answer array.\n\nIf the element is an array, we either add it to our answer array if we have reached our depth limit or recurse on the array.\n\nAs an example, consider `arr = [1, 2, [3, [4, 5], 6], 7], n = 1`. The red arrows in the following image demonstrates what a DFS traversal could look like.\n\n![dfs.png](https://assets.leetcode.com/users/images/04460f6e-2c01-4254-b8a5-cc1300b8e257_1681307783.6384199.png)\n\nThis "inorder" traversal (and tree traversals in general) can be done nicely with generators.\n\n# Complexity\n- Time complexity: $$O(\\ell)$$, where $\\ell$ is the length of the answer array.\n\n- Space complexity: $$O(\\ell)$$\n\n# Code\n```\ntype MultiDimensionalArray = (number | MultiDimensionalArray)[];\n\nfunction* inorder(arr: MultiDimensionalArray, n: number) {\n    // depth limit reached\n    if (n < 0) {\n        yield arr;\n        return;\n    }\n\n    // recursively DFS\n    for (const val of arr) {\n        if (typeof val === \'number\') {\n            yield val;\n        } else {\n            yield* inorder(val, n - 1);\n        }\n    }\n};\n\nvar flat = function (arr:  MultiDimensionalArray, n: number):  MultiDimensionalArray {\n    return [...inorder(arr, n)];\n};\n```
['Array', 'Depth-First Search', 'Recursion', 'TypeScript']