Iterative Post-order Traversal

28 Jan, 2020

As a reminder, the recursive Post-Order traversal of a binary tree goes as follows.

post_order(node):
    if node==nil:
        return
    left_result = post_order(node.left)
    right_result = post_order(node.right)
    return process(node, left_result, right_result)

The pattern is visit(left), visit(right), process(current).

Iterative Post-Order

I'm acquainted with two iterative post-order traversal algorithms. Both have tricky spots that one must be aware of.

• The first algorithm has two steps:
  • producing an intermediate pre-order stack,
  • which must then be unraveled as part of a secondary discovery step.
• The second algorithm is an adaptation of Iterative DFS (post-order traversal is a specialization of DFS for the binary tree).

Iterative post-order with a pre-order stack

The steps are as follows:

1. First, produce a pre-order stack with nodes arranged such that parents are inserted before their children. Also, if the left child should be processed before the right, the right child should be placed in that pre-order stack before the left.
2. Unpack the pre-order stack and process each node, storing the result in a stack of intermediary results.
3. If a node is nil, we simply push a terminal value (typically, nil) in the result stack.
4. Processing a non-nil node involves first retrieving (i.e. popping) the results of its children's processing from the intermediary result stack, then including those as part of the current computation, then storing the product of that computation back into the result stack.

iterative_post_order(node):
    pre_order_stack = make_pre_order_stack(node)
    result = []
    while pre_order_stack:
        node = pop(pre_order_stack)
        if node==nil:
            append(result, nil)
            continue
        left_result = pop(result)
        right_result = pop(result)
        process(node, left_result, right_result) | append(result, $0)
    return result[0]

One particularly tricky aspect of this algorithm is the careful stacking and unpacking of children. Consider in the above that left_result and right_result may not be interchangeable in how they're used during processing. It might therefore be important that when their values are popped from result, they end up in the appropriately labeled variables. The sequence is intricate.

• for left_result to be popped from result before right_result, it must be inserted after, i.e. result = [..., right_result, left_result, ...]
• it implies that right was popped from the pre_order_stack and processed before left, i.e. pre_order_stack = [..., left, right, ...]

Here's the implementation of make_pre_order_stack() accounting for this. Similarly to the above considerations, we must track how left and right are subsequently stacked, popped and restacked.

make_pre_order_stack(node):
    pre_order_stack = []
    temp_stack = [node]
    while temp_stack:
        node = pop(temp_stack)
        append(pre_order_stack, node)
        if not node:
            continue
        # right is added to temp_stack before left, so that it's popped from it and reinserted in pre_order_stack last.
        append(temp_stack, node.right)
        append(temp_stack, node.left)
    return pre_order_stack

There you have it. I've found that it's generally easy for me to remember that the order of appending is the reverse of the order of the popping from one function.

iterative_post_order(node):
    ...
    ...
        left_result = pop(result)
        right_result = pop(result)
    ...
    ...

make_pre_order_stack(node):
    ...
    ...
        append(temp_stack, node.right)
        append(temp_stack, node.left)
    ...
    ...

Iterative post-order (using iterative DFS)

This approach is a simplified adaptation of iterative DFS that presumes that the traversal will follow a valid binary tree pattern. It means that a node has no more than two children, there are no links leading back to ancestors, no cross-edges, and descendants are processed before ancestors. If those situations are to be considered, adapt the tree traversal from the more complete and constrained DFS iterative traversal, which makes provisions for such cases (see iterative DFS). In addition to tracking intermediary results like in the previous implementation, we also track a tate to identify a parent node ready for processing. Note that in this algorithm, we first peek at the discovery stack, we don't pop it. The pop only happens after the node is processed. This ensures that parent nodes are processed after their children. Alternatively, you could pop early, then reinsert the parent to the stack before its children.

iterative_post_order(node):
    discovery_stack = [node]
    result_stack = []
    while discovery_stack:
        node = peek(discovery_stack)
        if node==nil:
            append(result_stack, nil)
            pop(discovery_stack)
            continue
        if not node.ready:
            push(discovery_stack, node.right)
            push(discovery_stack, node.left)
            node.ready = true
            continue
        left_result = pop(result_stack)
        right_result = pop(result_stack)
        process(node, left_result, right_result) |> append(result_stack, $0)
        pop(discovery_stack)