This is a C Program to perform post order traversal. Time Complexity: O(n)
Here is source code of the C Program to Perform Postorder Non-Recursive Traversal of a Given Binary Tree. The C program is successfully compiled and run on a Linux system. The program output is also shown below.
// C program for iterative postorder traversal using one stack
#include <stdio.h>
#include <stdlib.h>
// Maximum stack size
#define MAX_SIZE 100
// A tree node
struct Node {
int data;
struct Node *left, *right;
};
// Stack type
struct Stack {
int size;
int top;
struct Node* *array;
};
// A utility function to create a new tree node
struct Node* newNode(int data) {
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// A utility function to create a stack of given size
struct Stack* createStack(int size) {
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->size = size;
stack->top = -1;
stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
return stack;
}
// BASIC OPERATIONS OF STACK
int isFull(struct Stack* stack) {
return stack->top - 1 == stack->size;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node) {
if (isFull(stack))
return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack) {
if (isEmpty(stack))
return NULL;
return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack) {
if (isEmpty(stack))
return NULL;
return stack->array[stack->top];
}
// An iterative function to do postorder traversal of a given binary tree
void postOrderIterative(struct Node* root) {
// Check for empty tree
if (root == NULL)
return;
struct Stack* stack = createStack(MAX_SIZE);
do {
// Move to leftmost node
while (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 root
if (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 functions
int main() {
// Let us construct the tree shown in above figure
struct Node* 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);
postOrderIterative(root);
return 0;
}
Output:
$ gcc PostorderNonRecursive.c $ ./a.out 4 5 2 6 7 3 1
Sanfoundry Global Education & Learning Series – 1000 C Programs.
advertisement
advertisement
Here’s the list of Best Books in C Programming, Data Structures and Algorithms.
Related Posts:
- Check Computer Science Books
- Watch Advanced C Programming Videos
- Practice BCA MCQs
- Check C Books
- Apply for Computer Science Internship