When Casey was talking about recursive tree traversal vs. non-recursive traversal using parent links vs. non-recursive traversal using a stack, he said that using an explicit stack will give you a breadth-first ordering. That's not right. Using a FIFO queue will give you a breadth-first ordering. Using a LIFO stack will give you a depth-first ordering just like the recursive version.

Here's an example. Say you're processing a node A that has children B, C, and D. So you push B, C, and D on the stack, let's just say in that order. Next loop iteration, you will pop D off the stack. Say D has children X and Y. Then you push X and Y on the stack, in that order, say. X and Y were pushed ahead of B and C, because it's a stack. So next iteration, you will pop Y off. In this way, you end up with a depth-first traversal.

Maybe Casey will see this and talk about it on Monday's stream :)

If I remember correctly I was doing something similar using two stacks.

I mean you always pop from one stack and push on another stack.

In your example you can begin with A on stack1, pop A and push its children on stack2.
In next iteration you pop B,C,D from stack2 and you can push all their children on stack1(this is the other stack which is always emptied in previous iteration so we can reuse it) and so on.