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 .