Given an n-ary tree, write code to flatten it and store the output in a list.

Flattening an n-ary tree into a list typically involves traversing the tree and collecting node values. The most common approaches are Depth-First Search (DFS) or Breadth-First Search (BFS), with DFS naturally yielding a preorder traversal.

Mechanics and Why

A Depth-First Search (DFS) approach recursively explores as far as possible along each branch before backtracking. For flattening, this means visiting a node, adding its value to the result list, and then recursively calling DFS on each of its children. This inherently produces a preorder traversal, where a node is processed before any of its descendants. This is often the desired "flattened" order for representing hierarchy linearly.

def flatten_dfs(node, result_list):
    if not node:
        return
    result_list.append(node.val)
    for child in node.children:
        flatten_dfs(child, result_list)

Alternatively, a Breadth-First Search (BFS) uses an iterative approach with a queue. You add the root to the queue, then repeatedly dequeue a node, add its value to the result, and enqueue all its children. This produces a level-order traversal, which is a different flattened sequence. If a specific preorder flatten is required, DFS is generally more straightforward. The "why" behind a preorder flatten is often to represent the hierarchical structure in a linear sequence, where parent nodes appear before their children. This is useful for serialization, reconstruction, or processing tasks where the parent-child relationship needs to be preserved sequentially.

Production Considerations and Trade-offs

In a production environment, handling None nodes or empty children lists is crucial for robustness. For very deep trees, recursive DFS might hit Python's recursion depth limit, necessitating an iterative DFS implementation using an explicit stack. BFS's queue can consume significant memory for very wide trees. Both approaches have a time complexity of O(N) where N is the total number of nodes, as each node is visited once. Space complexity for DFS is O(H) (H=height) due to the call stack, while BFS is O(W) (W=maximum width) for the queue, potentially making BFS more memory-intensive for wide trees and DFS for deep trees.

In the interview, also mention whether the output list should be mutable or immutable, and consider using a generator for extremely large trees to avoid materializing the entire list in memory.