# Inorder Traversal in Binary Tree Iteratively (without recursion)

In this article, we are going to find **what inorder traversal of a Binary Tree is and how to implement inorder traversal iteratively without using recursion?** We have provided the implementation in C++.

Submitted by Radib Kar, on July 30, 2020

In the earlier article on inorder traversal, we saw that inorder traversal is one of traversal which is based on depth-first search traversal. The basic concept for inorder traversal lies behind its name. **"In"** means between and that’s why the root is traversed in between its left & right subtree. The basic rule is:

- First, traverse the left subtree
- Then traverse the root
- Finally, traverse the right subtree

Of course, while traversing the subtrees we will follow the same order

We already saw a recursion based implementation. But here, we are going to discuss how to implement **without recursion using stack** **iteratively**.

When we are using recursion, what we are doing is traversing the left subtree always and then the current root and finally the right subtree. And we do this recursively for the subtrees. Like to traverse the right subtree, we again first traverse its left subtree, then the root and then again its right subtree if there any. Now to do this without recursion, we need stack which will do what recursion does. So the algorithm is:

1) Define a stack st first & set the current node as root. 2) While (current is not NULL or stack is not empty) //Going as much left as possible always While(current is not NULL) Push current to stack st Current=current->left End While Pop stack and print //traversal of nodes where left subtrees will be traversed first Set current=current->right //traversing right subtree End While

Dry Run using the above algorithm

Let's dry run the above example, using the above algorithm

We will use the value itself to represent the root

1) Define stack st & current is the root(7) 2) Processing while loop: ---------------------------------------------Iteration 1(outer loop)Current is not NULL Now to process the inner loop: Current is not NULL It will push 7 to stack Then, current=current->left=1 Current is not NULL It will push 1 to stack Then, current=current->left=0 Current is not NULL It will push 0 to stack Then, current=current->left=NULL Current is NULL, so inner loop breaks Now at this point, our stack is, 0 (top) 1 7 So pop from the stack and set current to that node So current is 0 and traverse/print it //Printed 0Now, current=current->right=NULL---------------------------------------------Iteration 2:Current is NULL but the stack is not empty Since Current is NULL thus it will not fall into the inner loop Now at this point, our stack is, 1(top) 7 So pop from the stack and set current to that node So Current is now 1 and traverse (print) it //printed 1 Now, current=current->right=1->right=subtree rooted with 3 ---------------------------------------------Iteration 3:Current is not NULL Since Current is not NULL thus it will fall into the inner loop Now to process the inner loop: Current is not NULL It will push 3 to stack Then, current=current->left=2 Current is not NULL It will push 2 to stack Then, current=current->left=NULL Current is NULL, so inner loop breaks Now at this point, our stack is, 2 (top) 3 7 So pop from the stack and set current to the popped node So current is 2 and traverse/print it //Printed 2 Now, current=current->right=NULL In this way, iterations will keep happening and will stop only when both conditions satisfy which are stack is empty and current is NULL. It indicates the end of traversal. I would suggest doing the dry run in paper and pen keeping the stack in front at every iteration.Finally we will get traversal as: 0 1 2 3 4 5 6 7 8 9 10

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; // tree node is defined class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int data) { val = data; left = NULL; right = NULL; } }; void inorder(TreeNode* root) { //base case if (root == NULL) return; stack<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); cout << cur->val << " "; cur = cur->right; } } int main() { //building the tree TreeNode* t = new TreeNode(7); t->left = new TreeNode(1); t->left->left = new TreeNode(0); t->left->right = new TreeNode(3); t->left->right->left = new TreeNode(2); t->left->right->right = new TreeNode(5); t->left->right->right->left = new TreeNode(4); t->left->right->right->right = new TreeNode(6); t->right = new TreeNode(9); t->right->left = new TreeNode(8); t->right->right = new TreeNode(10); printf("Inorder traversal of the above tree is:\n"); inorder(t); return 0; }

**Output:**

Inorder traversal of the above tree is: 0 1 2 3 4 5 6 7 8 9 10

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions