# Seamlessly simulated recursive procedure using stack

• This solution worked for all order traversal: preorder, inorder, postorder, you just need to move the data access line of code between the three sub-clause of `if`.

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
typedef struct stack {
void           *c;
struct stack   *next;
} Stack;

void create(Stack **ptop)
{
*ptop = NULL;
}

void push(Stack **ptop, void *c)
{
Stack   *tmp;

tmp = malloc(sizeof *tmp);
tmp->c = c;
tmp->next = *ptop;

*ptop = tmp;
}

void pop(Stack **ptop, void **c)
{
Stack   *tmp;

if (! *ptop) return;

tmp = *ptop;
if (c) *c = tmp->c;
*ptop = (*ptop)->next;
free(tmp);
}

void top(Stack **ptop, void **c)
{
*c = (*ptop)->c;
}

int empty(Stack **ptop)
{
return *ptop == NULL;
}

/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
int             *arr;
long            mark;
Stack           *s;
Stack           *pc;

create(&s);
create(&pc);
arr = malloc(10000 * sizeof *arr);
*returnSize = 0;

push(&s, root);
push(&pc, 0);
while (!empty(&s)) {
top(&s, &root);

if (!root) {
pop(&s, &root);
pop(&pc, &mark);
} else {
pop(&pc, &mark);

if (mark == 0) {
push(&s, root->left);
push(&pc, 1);
push(&pc, 0);
} else if (mark == 1) {
push(&s, root->right);
push(&pc, 2);
push(&pc, 0);
} else {
pop(&s, &root);
arr[(*returnSize)++] = root->val;
}
}
}

return arr;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.