In inorder traversal, left subtree is processed first followed by current node and then right subtree. In recursive version of inorder traversal stack(LIFO data structure) maintains references of left and right child.
In iterative version of inorder traversal we requires an external stack where references of left and right child is stored so that after visiting left subtree followed by current node, we can process right subtree. Here, with respect to each node, all left subtree is pushed into stack and process each node in loop. Loop is terminated once stack is empty.Refer following algorithm and sample code.
1. Insert root into stack, if root is not null.
2. Inside loop, do check for empty stack and terminate loop, if stack is empty.
Traverse given tree starting from current root until reaches leaf node, push all intermediate left subtree in stack.
If right child of popped node exist then push right child in stack and right child becomes current root.
Repeat steps 1 to 3 until stack is empty.
Time and space complexity :- Time complexity is order of O(n) and space complexity is O(n).
}// end inner while loop.