Recursion and Backtracking Questions

A streaming generator avoids building a full flattened list by yielding integers as they are discovered. Two common implementations: a recursive generator (simple, readable) and an iterative stack-based generator (avoids recursion depth limits).

Recursive generator:

def flatten_recursive(nested):
    """
    Yields ints from arbitrarily nested lists using recursion.
    """
    for item in nested:
        if isinstance(item, int):
            yield item
        elif isinstance(item, list):
            # delegate to recursive generator
            yield from flatten_recursive(item)
        else:
            raise TypeError("Expected int or list")

Iterative (stack-based) generator:

def flatten_iterative(nested):
    """
    Yields ints using an explicit stack to avoid recursion limits.
    We push an iterator for each list and traverse depth-first.
    """
    stack = [iter(nested)]
    while stack:
        try:
            item = next(stack[-1])
        except StopIteration:
            stack.pop()
            continue

        if isinstance(item, int):
            yield item
        elif isinstance(item, list):
            stack.append(iter(item))
        else:
            raise TypeError("Expected int or list")

Key points:

• Both are O(n) time (n = total number of elements including nested lists) and O(d) extra space (d = max nesting depth) for call stack or explicit stack.
• Recursive version is concise: "yield from" passes values up the chain but can hit Python recursion limit for deep nesting.
• Iterative version is slightly more verbose but robust for very deep structures (useful in production pipelines).
• Edge cases: empty lists, non-int elements (raise or skip based on requirements), extremely deep nesting.
• For large streaming pipelines, prefer the iterative approach to avoid RecursionError and to control memory use.

Approach: do an explicit stack-based depth-first traversal to avoid Python recursion limits. Push (current_mapping, prefix) pairs and iterate; when a value is a dict, push it onto the stack with an updated prefix; when it's a leaf, yield the dotted path. Allow configurable separator and treat non-string keys by converting to str. This yields paths lazily and handles arbitrarily deep nesting without recursion.

from collections import deque
from typing import Any, Dict, Iterator

def flatten_paths(d: Dict[Any, Any], sep: str = '.') -> Iterator[str]:
    """
    Yield dotted key paths for leaves in nested dict `d`.
    Non-dict values are considered leaves. Keys are stringified.
    Uses an explicit stack (DFS) to avoid recursion depth issues.
    """
    if not isinstance(d, dict):
        return
    stack = deque()
    stack.append((d, ""))  # (current_dict, prefix)

    while stack:
        current, prefix = stack.pop()
        for k, v in current.items():
            key = f"{prefix}{k}" if prefix == "" else f"{prefix}{sep}{k}"
            if isinstance(v, dict) and v:
                # push dict to continue traversal
                stack.append((v, key))
            else:
                yield key

Key points:

• Uses an explicit stack (deque) for iterative DFS; no recursion.
• Converts keys to strings implicitly via f-strings (ensure keys like ints are handled).
• Leaves include None and non-dict values; empty dicts produce no path unless you want to treat them as leaves (change logic accordingly).
  Time complexity: O(N) where N = number of key-value pairs visited. Space: O(d) for stack where d = max nesting depth (stack stores references only).
  Edge cases:
• Non-dict root: function returns nothing (adjust to yield "" or single path if desired).
• Keys containing the separator: choose a different separator or escape keys before joining.
• Preserve ordering: Python 3.7+ dicts preserve insertion order; stack DFS changes output order compared to recursion—use deque appendleft for BFS or different push/pop to control order.
  Alternative: use BFS with queue, or a generator that accepts a predicate for what counts as a leaf (e.g., treat lists as containers).