How to convert recursion algorithms into iteration version - Bo Song

How to convert recursion algorithms into iteration version - Bo Song
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.

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.

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.

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         }     } }

Read full article from How to convert recursion algorithms into iteration version - Bo Song