How to do it...

For postorder traversal of a binary tree, we need to apply three tasks—L, R, and V—on each of the tree nodes. These tasks are as follows:

• L means visit the left link
• R means visit the right link
• V means visit the node

To find out which tasks between L, R, and V are pending and which have already been performed, we will use two stacks: one for storing the node and another for storing an integer value of 0 or 1. Let's go over what 0 and 1 indicate:

• The value 0 indicates that the L task is done, while the R and V tasks are pending on the node.
• The value 1 means that the L and R tasks have been performed on the node and that only V is pending.

Follow these steps to perform postorder tree traversal:

1. A temporary node called temp is set to point at the root node of the tree.
2. Push the node that's being pointed at by temp to nodeArray and the value 0 to valueArray. The integer 0 in valueArray indicates that the R and V tasks are pending on the node.
3. Make the temp node point at the node where its left pointer is pointing.
4. If the temp is not pointing at NULL, go to step 2.
5. If temp reaches NULL, go to step 6.
6. Pop the node from nodeArray.
7. Pop the integer from valueArray.
8. If the popped integer value is 1, visit the node that is displaying the data member of the node. Then, go to step 6.
9. If the popped integer value is 0, go to step 10.
10. Push the node to nodeArray.
11. Push the integer 1 to valueArray to indicate that the L and R operations have been performed and that only V is pending.
12. Make the temp pointer point to where its right pointer is pointing.
13. If the temp pointer does not reach NULL, go to step 2.
14. If the temp pointer reaches NULL, go to step 6.

The program for creating a binary search tree and traversing it in postorder non-recursively is as follows:

//postordernonrec.c

#include <stdio.h>

#include <stdlib.h>

struct tree {
  int data;
  struct tree * right;
  struct tree * left;
};

struct stackstruc {
  int valueArray[15];
  struct tree * nodeArray[15];
};

struct stackstruc stack;
int top = -1;

struct tree * makeroot(int val);
void rightchild(struct tree * rootNode, int val);
void leftchild(struct tree * rootNode, int val);
void nontravpost(struct tree * node);
void pushNode(struct tree * node, int val);
struct tree * popNode();
int popVal();

int main() {
  struct tree * temp, * rootNode;
  int val;
  printf("Enter elements of tree and 0 to quit\n");
  scanf("%d", & val);
  rootNode = makeroot(val);
  scanf("%d", & val);
  while (val != 0) {
    temp = rootNode;
    while (1) {
      if (val < temp - > data) {
        if (temp - > left != NULL) {
          temp = temp - > left;
          continue;
        }
        leftchild(temp, val);
      }
      if (val > temp - > data) {
        if (temp - > right != NULL) {
          temp = temp - > right;
          continue;
        }
        rightchild(temp, val);
      }
      break;
    }
    scanf("%d", & val);
  }
  printf("\nTraversal of tree in Postorder without using recursion: \n");
  nontravpost(rootNode);
}

struct tree * makeroot(int val) {
  struct tree * rootNode;
  rootNode = (struct tree * ) malloc(sizeof(struct tree));
  rootNode - > data = val;
  rootNode - > right = NULL;
  rootNode - > left = NULL;
  return rootNode;
}

void leftchild(struct tree * rootNode, int val) {
  struct tree * newNode;
  newNode = (struct tree * ) malloc(sizeof(struct tree));
  newNode - > data = val;
  newNode - > left = NULL;
  newNode - > right = NULL;
  rootNode - > left = newNode;
}

void rightchild(struct tree * rootNode, int val) {
  struct tree * newNode;
  newNode = (struct tree * ) malloc(sizeof(struct tree));
  newNode - > data = val;
  newNode - > left = NULL;
  newNode - > right = NULL;
  rootNode - > right = newNode;
}

void nontravpost(struct tree * node) {
  struct tree * temp;
  int val;
  temp = node;
  while (1) {
    while (temp != NULL) {
      pushNode(temp, 0);
      temp = temp - > left;
    }
    while (top >= 0) {
      temp = popNode();
      val = popVal();
      if (val == 0) {
        if (temp - > right != NULL) {
          pushNode(temp, 1);
          temp = temp - > right;
          break;
        }
      }
      printf("%d\n", temp - > data);
      continue;
    }
    if ((temp == NULL) || (top < 0)) break;
    else continue;
  }
}

void pushNode(struct tree * node, int val) {
  top++;
  stack.nodeArray[top] = node;
  stack.valueArray[top] = val;
}

struct tree * popNode() {
  return (stack.nodeArray[top]);
}

int popVal() {
  return (stack.valueArray[top--]);
}

Now, let's go behind the scenes so that we can understand the code.