Postorder Traversal Without Using Recursion And Stack

Let's start by understanding the problem statement for this task.

You are given a tree, you have to print the post-order traversal without using recursion and stack.

Quick Think:

For creating a tree and printing its post-order traversal without using a stack, we can think of the following points:-

1. An alternative solution is to use a hash table which will keep track of the elements present in it, hash table helps you to prevent copying the element into the hash table and accepts only the unique entries.
2. For every new node to be pushed into the hash table should not be NULL and only unique elements should be present there.
3. As the node becomes NULL or the new node does not have a unique data value, then the node data is to be printed.

Algorithm:

For the algorithm for the above problem statement, we will define a function according to our will and pass the root node into it during its execution and perform the following steps:-

Step 1: We will define an unordered set with node data type along with a temporary node to store the root node reference.

Step 2: Now the operation of post-order traversal will continue until the next node traversed is not NULL and the data value of the next node is not present in the unordered set from before, to prevent the duplicate values to be inserted if both the conditions are satisfied or is ‘True’ then we go to step 3 else we go to step

Step 3: Now the condition to be checked is whether the left child node data is present in the unordered set or not and the data value of the left child is not NULL if it is ‘True’ then traverse through the left child node of the current node else go to step 4.

Step 4: If the previous step is ‘False’ then we move on to the right child node of the current node, it is checked whether the right child of the current node is not NULL and the right child data node must not be present in the unordered set if ‘True’ then traverse to the next right child node of the current node and go to step 5.

Step 5: If all the above conditions are not ‘True’ then the programmer needs to print out the data value of the current node and insert that data node to the unordered set and declare the temporary node to be the root node of the tree and the output leads to the post-order traversal without using any recursion and stack.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm,

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	struct node *left, *right;
};

/*Function to return the created 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 create the postorder traversal without stack and recursion by using a set. */
void createtree(struct node *root)
{
	struct node * temp;
	unordered_set<node*> set;
	temp = root;
	/*Check whether the current node is not NULL and is not duplicate. */
	while (temp && set.find(temp) == set.end())
	{
		/*Check whether the current node's left child is not NULL and is not duplicate. */
		if (temp->left && set.find(temp->left) == set.end())
			temp = temp->left;
		/*Check whether the current 's right child is not NULL and is not duplicate. */
		else if (temp->right && set.find(temp->right) == set.end())
			temp = temp->right;
		/*If all condition above fails then print the data and insert ot the set. */
		else
		{
			cout << temp->data << " ";
			set.insert(temp);
			temp = root;
		}
	}
}

/*Driver function to check the above algorithm. */
int main()
{
	struct node *root = newnode(8);
	root->left = newnode(3);
	root->right = newnode(10);
	root->left->left = newnode(1);
	root->left->right = newnode(6);
	root->left->right->left = newnode(4);
	root->left->right->right = newnode(7);
	root->right->right = newnode(14);
	root->right->right->left = newnode(5);
	createtree(root);
	return 0;
}

The Running Time Complexity Of The Above Algorithm is: O( n^2), as every time we insert a node we move back to it and declare it as the head.

The Output Of The Above Algorithm is: 1 4 7 6 3 5 14 10 8.

Explanation Of The Above Algorithm:

Let us consider the above example, the tree formed from form inserting the above nodes is as shown in the above diagram, now our task is to print the post-order traversal of it without using recursion or a stack.

• Now we will declare an unordered set to store our data nodes in it to keep track of the nodes already stored in the unordered set and declare a temporary node to keep track of the root node.
• Now we will traverse through each and every node and check whether the current node has a left child node or not since the root node has a left child and its data value is unique in the unordered set, since the condition is ‘True’ so we move to the left node of the current node after checking that the next node is not NULL and is unique in the unordered set.
• We are at the node with data 3 in the given tree above again we check that the left child node of the current node is not NULL and is unique in the unordered set, which is ‘True’ so we again move to the next left child of the current node which is the node with data value 1.

• Now since the next node of the current node with data value does not exist, so we will look into the next condition which is the right child of the current node exists, since there is no right child of the current node so, we will look into the third condition which is to print the current node data value and insert the node to the unordered set for future references and set the same temporary node as the root node, as shown in the above diagram.
• Now again we need to traverse from the beginning and check that the current node data value does not exist in the unordered set we're again following the above steps we reach the node with data value 3, and see that the left child node with value of 1 already exists in the unordered set, so we move to its right child which is 6.
• The parent node becomes the node with data 6 since this node has a left child, and it is unique to the unordered set, so we move to the left child node.

• Now the left child node becomes the parent node and since, this parent node does not have a left child or a right child so, the data value of the parent node is printed and inserted to the unordered set and again the temporary node becomes the root node of the tree as shown in the above diagram.
• Now again the tree is traversed using the root node and following the above steps once again reach the node with data 6 and see that the left child of the parent node already exists in the unordered set so, we move to the right child of the current node.

• Now the value of the right node is unique to the unordered set, so we print the data value of the right node and insert its data value to the unordered set and again set the temporary node as the root of the tree as shown in the above diagram.

• Now similarly following the above steps we reach the node with data value 6 and since it’s unique to the unordered set, we print its value and insert its value to the unordered set and again set the temporary node to the root of the tree as shown in the above diagram.

• Similarly, when we will traverse all the nodes of the left subtree, we will get a result as shown in the above diagram.

• Now we will move on to the right subtree and on a similar repetition of the above steps we get our final post-order traversal for the given tree as shown in the above diagram.