Question

Tree Traversals It should be noted that, in class, all traversal methods were written as recursive algorithm (i.e. at some point, the method called itself). It is possible to implement non-recursive versions of preorder, inorder, and postorder traversal methods mentioned in class. One intuitive way is by using a stack.
1) Give written pseudocode/explanation of :
a) How to build the tree such that a given non-recursive traversal method can be used.
b) Your algorithm for a non-recursive preorder, inorder, OR postorder traversal method (You only have to pick one)
2) Implement the above mentioned algorithms. Traversals should print out nodes in their required order.

Answer 1

In-order Non-recursive using stack -

#include<bits/stdc++.h>
using namespace std;
struct Node
{
   int val;
   struct Node *left;
   struct Node *right;
   Node (int key)
   {
       this->val=key;
       this->left=this->right=NULL;
   }
};

void printInorderIterative(struct Node *root)
{
   stack <Node *> s;
   struct Node *curr;
   curr=root;
   int flag=0;
   while(!flag)
   {
       if(curr)
       {
           s.push(curr);
           curr=curr->left;
       }
       else
       {
           if(!s.empty())
           {
               curr=s.top();
               s.pop();
               cout<<curr->val<<"\t";
               curr=curr->right;  
           }
           else
           {
               flag=1;
               return ;
           }
       }
   }
  
}
int main()
{
   struct Node *root;
   root=new Node(1);
   root->left=new Node(2);
   root->right=new Node(3);
   root->left->left= new Node(4);
   root->left->right=new Node(5);
   root->left->right->right= new Node(8);
   root->right->left= new Node(6);
   root->right->right= new Node(7);
   cout<<"Iterative Inorder Traversal is "<<endl;
   printInorderIterative(root);
   cout<<endl;
}

Postorder non-recursive using stack

#include <bits/stdc++.h>
using namespace std;

struct Node
{
   int data;
   Node *left, *right;
  
   Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};

void postorderIterative(Node* root)
{
   stack<Node*> s;
   s.push(root);
   stack<Node*> out;
   struct Node *curr;
   while(!s.empty())
   {
       curr=s.top();
       out.push(curr);
       s.pop();
       if(curr->right)
       {
           s.push(curr->right);
       }
       if(curr->left)
       {
           s.push(curr->left);
       }
   }
   while(!out.empty())
   {
       curr=out.top();
       cout<<curr->data<<" ";
       out.pop();
   }
}

int main()
{
   Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
   root->right->right = new Node(6);
   root->right->left->left = new Node(7);
   root->right->left->right = new Node(8);
   cout<<"Postorder traversal of the tree is "<<endl;
   postorderIterative(root);

   return 0;
}

Preorder non-recursive using stack

//preorder binary tree iterative traversal
#include<bits/stdc++.h>
using namespace std;

struct Node
{
   int data;
   Node *left, *right;
  
   Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};

void preOrderIterative(struct Node *root)
{
   stack <Node *> s;
   struct Node *curr;
   s.push(root);
   curr=s.top();
   while(!s.empty())
   {
       curr=s.top();
       s.pop();
       cout<<curr->data<<"\t";
       if(curr->right)
       {
           s.push(curr->right);
       }
       if(curr->left)
       {
           s.push(curr->left);
       }
   }
}
int main()
{
  
   Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->left->left = new Node(7);
root->right->left->right = new Node(8);
cout<<"Iterative Preoder traversal is "<<endl;
preOrderIterative(root);
return 0;
}