PostOrder Traversal in a binary tree

We discussed about the basic tree traversals in this post –

• Binary Tree Traversals

Lets take our own sample tree for understanding post-order traversal.

In Post-Order traversal, the root is visited after both sub-trees are completed. Post-order traversal is defined as follows:-

• Traverse the left sub-tree in post-order. (Step 1)
• Traverse the right sub-tree in post-order. (Step 2)
• Visit the root

The post-order traversal can then be defined in this way –

The nodes of the tree will therefore be in order – 4, 5, 2, 6, 7, 3, 1

The recursive version can be written as:-

void postOrderRecursive(struct binaryTreeNode * root)
{
    if(root)
    {
        // Post-order traversal of left sub-tree (Step 1)
        postOrderRecursive(root -> left);

        // Post-order traversal of right sub-tree (Step 2) 
        inOrderRecursive(root -> right);
	
        // Visit the root (Step 3)
        printf("%d ", root -> data);
    }
}

Non-recursive Post-order traversal

In pre-order and in-order traversals, after popping the stack element we do not need to visit the same vertex again. But in post-order traversal, each node is visited twice. That means, after processing left sub-tree we will be visiting the current node and also after processing the right sub-tree we will be visiting the same current node. But we should be processing the node during the second visit. Here the problem is how to differentiate whether we are returning from left sub-tree or right sub-tree ?

Trick for this problem is: after popping an element from the stack, check whether that element and right of top of the stack are same or not. If they are same then we are done with processing of left sub-tree and right sub-tree. In this case we just need top pop the stack one more time and print its data.

void postOrderNonRecursive(struct binaryTreeNode * root)
{
	// Create a new empty stack
	struct stackNode * S = NULL;
	
	// We need to run the loop until stack is not empty again
	while(1)
	{
		if(root != NULL)
		{
			// If a node exists, we add it to the stack
			S = push(S, root);
			root = root -> left; // Step 1
		}
		else
		{
			if(isStackEmpty(S))
			{
				return;
			}
			else
			{
				if(S -> top -> right == NULL)
				{
					root = S -> top;
					
					// Pop the stack
					S = S -> next;
					
					printf("%d ",root -> data); // Step 3
					
					if(root == S -> top -> right)
					{
						printf("%d ",S -> top -> data);
						S = S -> next;
					}
				}
			}
			if(!isStackEmpty(S))
				root = S -> top -> right; // Step 2
			else
				root = NULL;
		}
	}
	
	// We need to free the stack memory
	free(S);
}

Time Complexity:- O(n)
Space Complexity:- O(n)