# Inorder Tree Traversal Using Stack

“**Inorder Tree Traversal Using Stack**” is a binary tree traversal algorithm where we traverse the given tree in inorder fashion using stack data structure.

We have already discussed the recursive approach of the inorder traversal. Here, we implement the same algorithm using stack data structure.

The steps required to implement inorder tree traversal using stack data structure are as follows:

- Create an Empty Stack “st” of Node Type.
- Initialize currNode = Root Node.
- Loop until currNode is not empty or stack is not empty:
- Using Loop, set currNode = currNode -> left until current is NULL.
- Assign currNode = st.top()
- Pop out top node of stack
- Print “currNode -> data”
- Assign currNode = currNode -> Right.

#### C++ Program to implement Inorder Tree Traversal Using Stack is as follows:

/* C++ Program to implement inorder tree traversal using stack*/ #include<bits/stdc++.h> using namespace std; typedef struct Node { int data; struct Node *left; struct Node *right; Node(int ele) { data = ele; left = NULL; right = NULL; } } Node; /* Function to Implement inorder traversal */ void inorder(Node *root) { /* Check Base Condition */ if(root == NULL) return; /* Create an Empty Stack */ stack <Node *> st; Node *currNode = root; while(currNode != NULL || !st.empty()) { /* Reach the left most node of the tree */ while(currNode) { st.push(currNode); currNode = currNode -> left; } /* Assign Left to Left most node */ currNode = st.top(); /* Pop out the stack */ st.pop(); /* Print currNode data */ cout<<currNode -> data <<" "; /* Traverse right Subtree */ currNode = currNode -> right; } } int main() { /* Creating a Binary tree and inserting some nodes in it */ Node *root = NULL; root = new Node(1); root -> left = new Node(2); root -> right = new Node(3); root -> left -> left = new Node(4); root -> left -> right = new Node(5); root -> right -> left = new Node(6); root -> right -> right = new Node (7); root -> left -> right -> left = new Node(8); root -> right -> left -> right = new Node(9); /* Calling function to perform inorder traversal*/ cout<<"The Inorder Traversal of the Given Binary Tree is: "; inorder(root); }

**OUTPUT:**

The Inorder Traversal of the Given Binary Tree is: 4 2 8 5 1 6 9 3 7

**Related Posts:**

**Preorder Tree Trasversal Using Stack****Postorder Tree Traversal Using Stack****Vertical Order Tree Traversal****Top View of Binary Tree****Bottom View of Binary Tree****Delete Complete Binary Tree****Check if two trees are mirror Trees of Each Other****Convert Binary Tree to its Mirror Tree****Check if Binary Tree is Symmetric or Not****Print All Root to Leaf Paths in a Binary Tree****Introduction to Tree Data Structure****Binary Tree Traversals****Print All Leaf Nodes of a Binary Tree****Count Number of Nodes in a Binary Tree****Print Alternate Levels of Binary Tree****Maximum Width of Binary Tree****Level Order Tree Traversal****Left View of Binary Tree****Right View of Binary Tree****Compute Height of Binary Tree**