Post-order tree traversal in C

Post-order tree traversal without recursion in C

 

In postorder traversal , first we traverse the left subtree, then the right subtree and finally the root node. Postorder traversal is also used to get the postfix expression of an expression given.In this post , post-order tree traversal without recursion is discussed using one stacks.

C program for post order without using recursion

Algorithm :

  • Create an empty stack.
  • While root is not NULL, push root->right and then root to the stack.
  • And Set root as root->left.
  • If root becomes NULL, pop item from the stack and set it as root.
  • If the popped item has a right child and the right child is at top of stack, then remove the right child from stack, push the root back and set root as root’s right child.

  • Else print root’s data and set root as NULL.

  • Repeat the above two steps until stack is not empty.
Post order traversal without recursion in C

Code based on above algorithm :

#include <stdio.h>
#define MAX_SIZE 100

struct Node
{
int data;
struct Node *left, *right;
};

struct Stack
{
int size;
int top;
struct Node* *array;
};

struct Node* newNode(int data)
{
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}

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;
}

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];
}

void postOrderIterative(struct Node* root)
{
if (root == NULL)
return;

struct Stack* stack = createStack(MAX_SIZE);
do
{
while (root)
{
if (root->right)
push(stack, root->right);
push(stack, root);

root = root->left;
}

root = pop(stack);

if (root->right && peek(stack) == root->right)
{
pop(stack);
push(stack, root);
root = root->right;

}
else
{
printf("%d ", root->data);
root = NULL;
}
} while (!isEmpty(stack));
}


int main()
{

struct Node* root = NULL;
root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->left = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);
printf("Post order traversal of binary tree is :\n");
printf("[");
postOrderIterative(root);
printf("]");


return 0;
}
Output :

Post order traversal of binary tree is : 

[40 50 20 60 70 30 10]