Iteration vs. Recursion

Iteration obviously, unless your algorithm can't possibly be implemented any other way.

>>10
Given a node structure with ( parent, left, right ), the following is a possibly correct prefix traversal of a binary search tree which is tail-return optimized to not use the stack.

Similar forms exist for in-order and post-order traversals (you move the call to func around).

def _iterate( curr, last, func ):
    if not curr.parent: return None
    if curr.parent == last:
        func( curr )
        if curr.left:
            return _iterate( curr.left, curr, func )
        elif curr.right:
            return _iterate( curr.right, curr, func )
        else
            return _iterate( last, curr, func )
    elif curr.left and curr.left == last:
        if curr.right:
            return _iterate( curr.right, curr, func )
        else:
            return _iterate( curr.parent, curr, func )
    else:
        return _iterate( curr.parent, curr, func )

Obviously unoptimized, but you get the drift. Since the traversal (when viewed as an undirected graph) goes across each edge exactly twice (once in each direction), we can store the state of the traversal simply as which edge we're at, and which direction we're heading. This can be represented as two node pointers (the ones which compose the edge) ordered respecting the current step's 'direction'.

For more details please refer to The Structure and Interpretation of Computer Programs.