Question

Design a nonrecursive post order traversal algorithm.

1.Use the linked representation for the binary tree to be traversed.

2.Except left, right, and data fields, there are no other fields in a node.

3.After the traversal the tree should remain intact.

4.Use only one stack.

5.You can’t push anything other than nodes into the stack.

Answer 1

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 10
struct BinaryTreeNode
{
        int data;
        struct BinaryTreeNode *left;
        struct BinaryTreeNode *right;
};
struct Queue
{
        struct BinaryTreeNode *node;
        struct Queue *next;
};
struct ArrayStack
{
        int top;
        int capacity;
        struct BinaryTreeNode **array;
};
struct ArrayStack *CreateStack()
{
        struct ArrayStack *S = malloc(sizeof(struct ArrayStack));
        if(!S)
        {
                return NULL;
        }
        S -> capacity = MAXSIZE;
        S -> top = -1;
        S -> array = malloc(S -> capacity * sizeof(struct BinaryTreeNode));
        if(!S -> array)
        {
                return NULL;
        }
        return S;
}
int IsEmptyStack(struct ArrayStack *S)
{
        return S -> top == -1;
}
int IsFullStack(struct ArrayStack *S)
{
        return S -> top == S -> capacity - 1;
}
void Push(struct ArrayStack *S, struct BinaryTreeNode *data)
{
        if(IsFullStack(S))
        {
                printf("Stack Overflow\n");
        }
        else
        {
                S -> array[++S -> top] = data;
        }
}
void Pop(struct ArrayStack *S)
{
        if(IsEmptyStack(S))
        {
                printf("Stack is Empty\n");
        }
        else
        {
                S -> array[S -> top--];
        }
}
struct BinaryTreeNode *Top(struct ArrayStack *S)
{
        return S -> array[S -> top];
}
void DeleteStack(struct ArrayStack *S)
{
        if(S)
        {
                if(S -> array)
                {
                        free(S->array);
                }
                free(S);
        }
}
struct Queue *Q = NULL;
struct BinaryTreeNode *root = NULL;
void EnQueue(struct BinaryTreeNode *node)
{
        struct Queue *newNode = (struct Queue*)malloc(sizeof(struct Queue));
        newNode->node = node;
        newNode->next = NULL;
        if(Q == NULL)
        {
                Q = newNode;
        }
        else
        {
                struct Queue *current;
                current = Q;
                while(current->next!=NULL)
                {
                        current = current -> next;
                }
                current->next = newNode;
        }
}
struct BinaryTreeNode* DeQueue()
{
        if(Q == NULL)
        {
                return NULL;
        }
        else
        {
                struct Queue *current;
                current = Q;
                Q = Q->next;
                return current->node;
        }
        
}
int IsEmptyQueue()
{
        if(Q == NULL)
        {
                return 1;
        }
        else
        {
                return 0;
        }
}
void InsertInBinaryTree(int data)
{
        struct BinaryTreeNode *temp;
        struct BinaryTreeNode *newNode;
        newNode = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
        newNode->data = data;
        newNode->left = newNode->right = NULL;
        if(root == NULL)
        {
                root = newNode;
                return;
        }
        else
        {
                EnQueue(root);
                while(!IsEmptyQueue())
                {
                        temp = DeQueue();
                        if(temp->left)
                        {
                                EnQueue(temp->left);
                        }
                        else
                        {
                                temp->left = newNode;
                                Q = NULL;
                                return;
                        }
                        if(temp->right)
                        {
                                EnQueue(temp->right);
                        }
                        else
                        {
                                temp->right = newNode;
                                Q = NULL;
                                return;
                        }
                }
        }       
        Q = NULL;
}
void PostOrderNonRecursive(struct BinaryTreeNode *root)
{
        struct ArrayStack *S = CreateStack();
        struct BinaryTreeNode *previous = NULL;
        do
        {
                while(root != NULL)
                {
                        Push(S,root);
                        root = root-> left;
                }
                while(root == NULL && !IsEmptyStack(S))
                {
                        root = Top(S);
                        if(root -> right == NULL || root -> right == previous)
                        {
                                printf("%d->",root->data);
                                Pop(S);
                                previous = root;
                                root = NULL;
                        }
                        else
                        {
                                root = root -> right;
                        }
                }
        }while(!IsEmptyStack(S));
        printf("\n");
}
int main()
{
        InsertInBinaryTree(1);
        InsertInBinaryTree(2);
        InsertInBinaryTree(3);
        InsertInBinaryTree(4);
        InsertInBinaryTree(5);
        InsertInBinaryTree(6);
        InsertInBinaryTree(7);
        PostOrderNonRecursive(root);
}

If you have any doubts please feel free to ask in comments and please don't dislike.