Postorder Traversal in Binary Tree

In Postorder traversal, first we have to visit the left subtree ,then visit the right subtree and then root .

Process is defined as follows :

• process the left subtree
• process the right subtree.
• Visit the root node.

Working Process of Postorde Traversal

Code Implementation of Postorder Traversal

Inorder traversing can be implement in two ways :
1- Recursive Implementation
2- Non-Recursive Implementation.

• Debug the recursive and Non-recursive code with the below Binary tree :

Recursive Implementation of Postorder Traversal

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
struct BinaryTreeNode                  // Node Structure Initialization
{
	char  data;                         // for data element
	struct BinaryTreeNode* left;   // for storing the address of left child
	struct BinaryTreeNode* right;  // for storing the address of right child
};
// PostOrder Traversing method.
void PostOrderTraversing(struct BinaryTreeNode* rootNode)
{
	if (rootNode)
	{
		PostOrderTraversing(rootNode->left);
		PostOrderTraversing(rootNode->right);
		std::cout << rootNode->data << " ";
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinaryTreeNode* A = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* B = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* C = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* D = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* E = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	//address arrangement.
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	//leaf node has zero child.
	C->left = NULL;
	C->right = NULL;
	D->left = NULL;
	D->right = NULL;
	E->left = NULL;
	E->right = NULL;
	//Data Initilization.
	A->data = 'A';
	B->data = 'B';
	C->data = 'C';
	D->data = 'D';
	E->data = 'E';
	// call the function to print the PostOrder Sequence
	printf("PostOrder Traversal will be : ");
	PostOrderTraversing(A);
	_getch();
	return 0;
}

Non-Recursive Implementation of Postorder Traversal

#include <stdio.h>
#include <iostream>
#include<conio.h>
#include<math.h>
#include<stdlib.h>
#include<stack>
struct BinaryTreeNode                  // Node Structure Initialization
{
	char  data;                         // for data element
	struct BinaryTreeNode* left;   //for storing the address of left child
	struct BinaryTreeNode* right;  // for storing the address of right child
};
// PostOrder Traversing method.
void PostOrderTraversing(struct BinaryTreeNode* rootNode)
{
	//For Stack ,we used stack library of STL.
	std::stack <struct BinaryTreeNode*> StackForRoot;
	struct BinaryTreeNode* PreviousNode = NULL;
	while (true)
	{
		while (rootNode)
		{
			//store the rootNode of all subtree into the stack.
			StackForRoot.push(rootNode);
			rootNode = rootNode->left;
		}
		//When no node is availabe in Left then pop the stack
		if (!StackForRoot.empty())
		{
			//Store the top value of stack.
			rootNode = StackForRoot.top();
			if (rootNode->right!= NULL && PreviousNode!= rootNode->right)
			{
				rootNode = rootNode->right;
			}
			else
			{
				//Pop the top value.
				StackForRoot.pop();
				//print the node Data.
				std::cout << rootNode->data << " ";
				PreviousNode = rootNode;
				rootNode = NULL;
			}
		}
		else
			break;
	}
}
int main()
{
	//initialize 5 node to create the binary tree.
	struct BinaryTreeNode* A = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* B = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* C = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* D = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	struct BinaryTreeNode* E = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
	//address arrangement.
	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	//leaf node has zero child.
	C->left = NULL;
	C->right = NULL;
	D->left = NULL;
	D->right = NULL;
	E->left = NULL;
	E->right = NULL;
	//Data Initilization.
	A->data = 'A';
	B->data = 'B';
	C->data = 'C';
	D->data = 'D';
	E->data = 'E';
	// call the function to print the Preorder Sequence
	printf("PostOrder Traversal will be : ");
	PostOrderTraversing(A);
	_getch();
	return 0;
}

 Time & Space Complexity of Postorder Traversal

• For Recursive Implementation : Time Complexity will be O(n),
  and Space Complexity will be O(n).
• For Non-Recursive Implementation : Time Complexity will be O(n),and Space Complexity will be O(n).