Inorder Traversal Without Recursion (can be used for DFS without recursion)

/*
In order traversal without recursion using Morris Traversal.

Algo :

1. Initialize current as root
2. While current is not NULL
    If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
    Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left
*/


#include "iostream"
using namespace std;
struct Node
{
     int data;
     Node * left;
     Node * right;
     Node() : left(NULL),right(NULL),data(0) { }
     Node(Node * l,Node * r,int d) : left(l),right(r),data(d) { }
     Node(int d) : left(NULL),right(NULL),data(d) { }
     ~Node()
    {
          if(left)
               delete left;
          if(right)
               delete right;
     }
};

void removeNodes(Node * root)
{
     if(root)
    {
          if(root->right)
          {
               removeNodes(root->right);
               root->right = NULL;
             }
          if(root->left)
          {
               removeNodes(root->left);
               root->left = NULL;
          }
          delete root;
     }
}

// Morris Traversal
void InorderTraversal(Node * root)
{
     Node * current, * pre;
     if(root == NULL)
          return;

     current = root;
     while(current)
     {
           if(current->left == NULL)
          {
                cout<< current->data <<" ";
                current = current->right;
           }else
          {
                // reArrange
                pre = current->left;
                while(pre->right != NULL && pre->right != current)
                     pre = pre->right;
                if(pre->right == NULL)
               {
                     pre->right = current;
                     current = current->left;
                }
       // print data and remove reArrangement
                else
               {
                     pre->right = NULL;
                    cout<< current->data << " ";
                    current= current->right;
                }
          }
      }
}


int main()
{
     Node * root = new Node(7);
     root->left = new Node(5);
     root->right = new Node(9);
     root->right->left = new Node(8);
     root->right->right = new Node(10);

     root->left->left = new Node(3);
     root->left->right = new Node(6);
     root->left->left->left = new Node(1);
     root->left->left->right = new Node(4);
     root->left->left->left->right = new Node(2);
   
     InorderTraversal(root);

     removeNodes(root);
     return 0;
}