In technical interviews, many candidates are asked to implement recursion algorithms using iteration. Generally, an algorithm implemented in iteration will run faster than that in recursion, since it avoids the overhead of function call. With the help of a stack and careful algorithm design, we can convert all recursion algorithms to its corresponding iteration version.

First, let’s start with a general recursion template code written in C++. It is a recursive traversal in binary tree.

class TreeNode
{
public:
   TreeNode * left, * right;
   int val;
   TreeNode(int v): val(v), left(nullptr), right(nullptr){}
};

void recr_traverse (TreeNode * root){
    if(root == nullptr){
        return ;
    }
    // preorder traveral
    // do some works here
    
    recr_traverse(root->left);
    // inorder traversal
    // do some works here

    recr_traverse(root->right);
    // post order traveral
    // do some works here
}

There are three types of recursion, distinguished by the visiting order – preorder, postorder and inorder. In another word, we visit every node for three times. We may visit a node coming from its parent node (preorder), from its left child (inorder), or from its right child(postorder).

Therefore, in the iteration code, we need to attach an attribute to each node indicating how many times we have visited this node. In our design, we use an integer to store this information and use an stack to simulate function call stack in system.

Following is the iteration version of previous recursion code. They are functionally equal.

#include <iostream>
#include <vector>
#include <stack>
class TreeNode
{
public:
   TreeNode * left, * right;
   int val;
   TreeNode(int v): val(v), left(nullptr), right(nullptr){}
};

void iter_traverse (TreeNode * root){
    // When we visit current node at the first time, which means we come from its parent node, set pair.second to 1.
    // We set pair.second to 2 which indicates we come to this node from its left child.
    // Otherwise pair.second is set to 3 meaning we come to this node from its right child.
    stack<pair<TreeNode*, int> > s;
    if(root == nullptr){
        return ;
    }
    s.push(make_pair(root, 1));
    while(!s.empty()){
        TreeNode * p = s.top().first;
        int flag = s.top().second;
        s.pop();
        if(flag == 1){
            // preorder traversal
            // do some works here

            s.push(make_pair(p, 3));
            if(p->right){
                s.push(make_pair(p->right, 1));
            }
            s.push(make_pair(p, 2));
            if(p->left){
                s.push(make_pair(p->left, 1));
            }
        }else if(flag == 2){
            // inorder traversal
            // do some works here

        }
        else{
            // postorder traversal 
            // do some works here
        }
    }
}

It needs to be clarified that we need to push the right child first, then current node itself, and finally the left child, since elements in stack follow first-in-last-out order.