// C program for iterative postorder traversal using one stack#include<stdio.h>#include<stdlib.h>// Maximum stack size#define MAX_SIZE 100// A tree nodestructNode
{int data;
structNode *left, *right;
};
// Stack typestructStack
{int size;
int top;
structNode* *array;
};
// A utility function to create a new tree nodestruct Node* newNode(int data){
structNode* node = (structNode*) malloc(sizeof(structNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
// A utility function to create a stack of given sizestruct Stack* createStack(int size){
structStack* stack = (structStack*) malloc(sizeof(structStack));stack->size = size;
stack->top = -1;
stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
returnstack;
}
// BASIC OPERATIONS OF STACKintisFull(struct Stack* stack){ returnstack->top - 1 == stack->size; }
intisEmpty(struct Stack* stack){ returnstack->top == -1; }
voidpush(struct Stack* stack, struct Node* node){
if (isFull(stack))
return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack){
if (isEmpty(stack))
returnNULL;
returnstack->array[stack->top--];
}
struct Node* peek(struct Stack* stack){
if (isEmpty(stack))
returnNULL;
returnstack->array[stack->top];
}
// An iterative function to do postorder traversal of a given binary treevoidpostOrderIterative(struct Node* root){
// Check for empty treeif (root == NULL)
return;
structStack* stack = createStack(MAX_SIZE);do
{
// Move to leftmost nodewhile (root)
{
// Push root's right child and then root to stack.if (root->right)
push(stack, root->right);
push(stack, root);
// Set root as root's left child
root = root->left;
}
// Pop an item from stack and set it as root
root = pop(stack);
// If the popped item has a right child and the right child is not// processed yet, then make sure right child is processed before rootif (root->right && peek(stack) == root->right)
{
pop(stack); // remove right child from stack
push(stack, root); // push root back to stack
root = root->right; // change root so that the right// child is processed next
}
else// Else print root's data and set root as NULL
{
printf("%d ", root->data);
root = NULL;
}
} while (!isEmpty(stack));
}
// Driver program to test above functionsintmain(){
// Let us construct the tree shown in above figurestructNode* root = NULL;
root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printf("Post order traversal of binary tree is :\n");
printf("[");
postOrderIterative(root);
printf("]");
return0;
}