Let's start by understanding the problem statement for this task.
You are given a tree, you have to perform an in-order traversal and print the data nodes of the tree without using recursion.
Quick Think:
For printing the data node of a given tree through in order traversal without recursion, you need to look at the following points:-
- You will need a stack to store the data nodes and print them one by one because for in-order traversal you always start with the leftmost node of the left subtree present in the tree and stack works on the principle of LIFO (Last In First Out).
- You will need to check initially that the stack is not empty or the node which is going to be pushed into the stack is not NULL because if the node is NULL or the stack is empty then the process has to be terminated.
- Now next you have to see that while pushing the left nodes of the left subtree into the stack the nodes are not NULL, if it is NULL the process has to be terminated.
Algorithm:
Step 1: Create a stack and a temporary node to store the root node of the given tree.
Step 2: Check whether the stack is not empty or the root node is not NULL by using a while loop as the operation has to be continued until the stack is not empty or the root node is not NULL if NULL then go to step 7.
Step 3: Check whether the node to be pushed into the stack is not NULL, by using a while loop as the process of pushing the nodes to the stack will continue till the nodes are not NULL if NULL then go to step 5.
Step 4: Keep pushing the nodes to the stack and keep moving to the leftmost node of the left subtree one by one until the node found is NULL.
Step 5: Terminate the loop condition where the node is checked to be NULL, now we have the left nodes of the left subtree in the stack.
Step 6: Now we will print the value of the popped node and move to the right child of the popped node similarly the loop with the condition in step 2 is checked followed by the loop condition in step 3.
Step 7: Now, if the condition in Step 2 is not true, then the loop gets terminated.
Implementation Of The Above Algorithm:
Implementation of the above-given algorithm is as follows:-
#include <bits/stdc++.h>
using namespace std;
struct node
{
int data;
struct node *left, *right;
};
/*Function to allocate memory for new nodes. */
struct node* newnode(int data)
{
struct node * node;
node = (struct node *) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
/*Function to print inorder traversal without recursion using a stack. */
void inorder_traversal(struct node *root)
{
stack<node*> s;
struct node *temp = root;
/*Condition to check the node to be pushed to the stack and the stack being non empty. */
while (!s.empty() || temp != NULL)
{
/*Condition to check the node to be pushed into the stack. */
while (temp != NULL)
{
s.push(temp);
temp = temp->left;
}
/*Popping out the top node form the stack and printing out the value. */
temp = s.top();
s.pop();
cout << temp->data << " ";
temp = temp->right;
}
}
int main()
{
/*Constructed binary tree is
10
/ \
23 37
/ \
41 50
*/
struct node *root = newnode(10);
root->left = newnode(23);
root->right = newnode(37);
root->left->left = newnode(41);
root->left->right = newnode(50);
inorder_traversal(root);
}
The Running Time Complexity Of the Above Program is: O(N)
The Output Of The Above Program is: 41 23 50 10 37.
Explanation Of The Above Code:
Now let us consider a problem as shown in the above diagram where we have to print the data value of the nodes by in order traversal without recursion of the given tree we will test the above program:
- Now here at first, we will define an empty stack along with a NULL node which will take the value of the root node at the beginning, here the node with data value 10 is the root node.
- Since the root node, in this case, is not NULL, our loop condition is ‘True’ which checks either condition whether the stack is not empty or the node is not NULL.
- Further, the next loop condition is ‘True’ as well, which says that the node should not be NULL.
- Now since the root node is not NULL so, the node with data 10 is pushed into the stack as shown in the above diagram.
- Now since we can clearly see from the diagram that the root node has a left child in its left subtree, and it’s not NULL, so we will push the left child of the root node to the stack as shown in the above diagram.
- Now also the left child of the current node is not NULL, so we will push its left child to the stack as shown in the above diagram.
- Now the node with data value 41 does not have a left child node so, the condition of the node to ‘not be empty’ is ‘
False’ and hence the node is popped out of the stack and its data value is printed. Now since this node does not have a right child and ‘it is NULL’ so, we move to the next node in the stack as the condition of the stack to ‘not be empty’ or the node to ‘not be NULL’ is ‘True’.
- Now the node with data value 23 is popped out of the stack and its data value is printed as shown in the above diagram.
- Now since this node has a right child and is ‘not NULL’ so, according to our algorithm the condition of the node to ‘not be
NULL’ is ‘True’ along with the condition that the stack is ‘not empty’ so, we will push the node with data value 50 into the stack as shown in the above diagram.
- Now since the node data with value 50 does not have a left child and ‘is NULL’ so, the condition of the node to ‘not be NULL’ is ‘False’ and hence the node is popped out of the stack and its data value is printed as shown in the above diagram.
- Now since the node with data value 50 does not have a right child as ‘is NULL’ so the condition of the node to ‘not be NULL’ is ‘False’ and the condition that the stack is ‘not empty’ is ‘True’ so, the node with data value 10 is popped out, and its data value is printed as shown in the above diagram.
- Now since the node with a data value, of 37 does not have a left child and ‘is
NULL’ so, the condition of the node to ‘not be NULL’ is ‘False’ and the node with data value 37 is popped out, and its data value is printed as shown in the above diagram.
- Now since the stack is empty and the next node is NULL as well, so the program gets terminated with the output as shown in the above diagram.
