Is it possible to iterate through a binary tree using iteration instead of recursion?

In school, when we need to iterate through a tree (e.g. binary search tree), we were always taught to iterate through the tree recursively.

Since every recusion can be written as iteration, is it possible to solely use iteration to access the elements of a tree?

I am asking this in context of C++

Solution

Yes.

For each node you process, store the children into a queue. This goes on for the rest of the nodes in the same level. After processing all the nodes in that level, you then process the queued children. In turn, you store the children's children into the queue. This goes on until you hit the bottom.

For instance the following:

      D
  B       F 
A   C   E   G

// 1
Current: D
Queue: B, F

// 2
Current: B, F
Queue: A, C, E, G

// 3
Current: A, C, E, G
Queue: no more!

Iteration is much more intricate than recursion since you need to implement a queue (if not provided) as well as some additional logic for unbalanced trees. However, iteration is more "memory-friendly" because your queue is just a bunch of pointers to nodes whereas recursion eats up the stack per call.