recursion and yield return

Get a list of nodes given a tree structure of nodes.

A
|
+--B
|
+--C
|  |
|  +--D
|
+--E

Result:

{ A, B, C, D, E }

Data structure:

node:
    string name
    list<node> children

Using recursion:

traverse(root):
    list = new
    Get(root, list)
    return list

// with list
Get(node, list):
    list.add(node)
    if node.children == null:
        return
    foreach child in node.children:
        Get(child, list)

Using recursion and yield return:

traverse(root):
    return Get(root)
    
// with yield return
Get(node):
    yield return node
    if node.children == null:
        yield break
    foreach child in node.children:
        foreach n in Get(child):
            yield return n

But it is inefficient when the tree is deep as every method call creates an iterator (see this), i.e. O(n) iterators. So the work-around is to not use recursion and save nodes in a stack with O(n) space and O(logn) iterators.

traverse(root):
    return Get(root)
    
// without recursion, with yield return
Get(node):
    stack = new
    stack.push(node)
    while !stack.empty():
        var n = stack.pop()
        yield return n
        if n.children == null:
            continue
        // reverse to preserve children order
        foreach child in n.children.reverse():
            stack.push(child)

[Hat tip to RT, JS, EL]