Hey there How is it going hope everything is fine .

Today I'm going to explain the inorder traversal in iterative manner .

I know you will feel like inorder traversal in recursion such an easy code

but this can be a follow up interview question for that recursive one

let me just tell you the recursive one ( which is easy ) first then we will solve it

iteratively .

RECURSIVE

In recursive approach we will 
      first  move  left
      then  process the data
      then  move right

void inOrder(Node* root){
        if( !root) return ;

        inOrder( root->left );
        cout<< root->data <<" ";
        inOrder( root->right );
}

ITERATIVE

Iterative approach helps you how recursion works internally and how

stack memory is manipulated internally .

Basically In these approach we first traverse left until it becomes NULL

and then we pop the node and push its right and continue same steps

Let me explain briefly

STEPS :

1.  Initialize two variables 
    stack<Node*> stack;  // as recursion internally uses stack
    Node* curr  = root ; // traversing pointer

2. Go as left as possible and push the nodes into the stack
     while(!curr){
             stack.push(curr);
             curr = curr->left;
     }

3. Then pop the stack push the right node of popped node
       curr = stack.top();
       stack.pop();
       stack.push(curr->right);

4. Repeat the steps 2 and 3 untill curr is not null and stack becomes empty     

CODE :

      void inOrder(Node* root)
     {
            stack<Node*> stack;
            Node* curr =  root;
            while( !stack.empty()  || curr ){
                 while(curr){
                       stack.push(curr);
                       curr = curr->left;   
                  }
            curr = stack.top();
            stack.pop();
            cout<<curr->data;
            curr = curr->right;
          }
     }

TIME COMPLEXITY : O(N)  
SPACE COMPLEXITY: O(H)

  where N is  noof nodes
  where H is the height of the tree 
 In worst case H is equals to N in case of skewed binary 
 tree so space complexity can be O( N )

Thank you for reading . Hope you understand it .