{"id":27636,"date":"2018-04-09T20:16:08","date_gmt":"2018-04-09T14:46:08","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27636"},"modified":"2018-09-16T13:24:10","modified_gmt":"2018-09-16T07:54:10","slug":"c-algorithm-iterative-postorder-traversal-set-2-using-one-stack","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-algorithm-iterative-postorder-traversal-set-2-using-one-stack\/","title":{"rendered":"C Algorithm – Iterative Postorder Traversal | Set 2 (Using One Stack)"},"content":{"rendered":"

We have discussed a simple iterative postorder traversal using two stacks in the previous post. In this post, an approach with only one stack is discussed.<\/span><\/p>\n

The idea is to move down to leftmost node using left pointer. While moving down, push root and root\u2019s right child to stack. Once we reach leftmost node, print it if it doesn\u2019t have a right child. If it has a right child, then change root so that the right child is processed before.<\/p>\n

Following is detailed algorithm.<\/p>\n

1.1 Create an empty stack\r\n2.1 Do following while root is not NULL\r\n    a) Push root's right child and then root to stack.\r\n    b) Set root as root's left child.\r\n2.2 Pop an item from stack and set it as root.\r\n    a) If the popped item has a right child and the right child \r\n       is at top of stack, then remove the right child from stack,\r\n       push the root back and set root as root's right child.\r\n    b) Else print root's data and set root as NULL.\r\n2.3 Repeat steps 2.1 and 2.2 while stack is not empty.<\/pre>\n
Let us consider the following tree<\/p>\n
Following are the steps to print postorder traversal of the above tree using one stack.<\/p>\n
1. Right child of 1 exists. \r\n   Push 3 to stack. Push 1 to stack. Move to left child.\r\n        Stack: 3, 1\r\n\r\n2. Right child of 2 exists. \r\n   Push 5 to stack. Push 2 to stack. Move to left child.\r\n        Stack: 3, 1, 5, 2\r\n\r\n3. Right child of 4 doesn't exist. '\r\n   Push 4 to stack. Move to left child.\r\n        Stack: 3, 1, 5, 2, 4\r\n\r\n4. Current node is NULL. \r\n   Pop 4 from stack. Right child of 4 doesn't exist. \r\n   Print 4. Set current node to NULL.\r\n        Stack: 3, 1, 5, 2\r\n\r\n5. Current node is NULL. \r\n    Pop 2 from stack. Since right child of 2 equals stack top element, \r\n    pop 5 from stack. Now push 2 to stack.     \r\n    Move current node to right child of 2 i.e. 5\r\n        Stack: 3, 1, 2\r\n\r\n6. Right child of 5 doesn't exist. Push 5 to stack. Move to left child.\r\n        Stack: 3, 1, 2, 5\r\n\r\n7. Current node is NULL. Pop 5 from stack. Right child of 5 doesn't exist. \r\n   Print 5. Set current node to NULL.\r\n        Stack: 3, 1, 2\r\n\r\n8. Current node is NULL. Pop 2 from stack. \r\n   Right child of 2 is not equal to stack top element. \r\n   Print 2. Set current node to NULL.\r\n        Stack: 3, 1\r\n\r\n9. Current node is NULL. Pop 1 from stack. \r\n   Since right child of 1 equals stack top element, pop 3 from stack. \r\n   Now push 1 to stack. Move current node to right child of 1 i.e. 3\r\n        Stack: 1\r\n\r\n10. Repeat the same as above steps and Print 6, 7 and 3. \r\n    Pop 1 and Print 1.<\/pre>\n
C Programming:<\/strong><\/p>\n
 
 <\/div> 
\/\/ C program for iterative postorder traversal using one stack#include <stdio.h>#include <stdlib.h> \/\/ Maximum stack size#define MAX_SIZE 100 \/\/ A tree nodestruct Node{    int data;    struct Node *left, *right;}; \/\/ Stack typestruct Stack{    int size;    int top;    struct Node* *array;}; \/\/ A utility function to create a new tree nodestruct 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 sizestruct 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 STACKint 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 treevoid 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 functionsint 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);    printf("Post order traversal of binary tree is :\\n");    printf("[");    postOrderIterative(root);    printf("]");          return 0;}<\/code><\/pre> <\/div>\n
Output:<\/strong><\/p>\n
Post Order traversal of binary tree is\r\n[4, 5, 2, 6, 7, 3, 1]<\/pre>\n","protected":false},"excerpt":{"rendered":"
C Algorithm – Iterative Postorder Traversal | Set 2 (Using One Stack) – Stack – We have discussed a simple iterative postorder traversal using two stacks <\/p>\n","protected":false},"author":1,"featured_media":31284,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,79607],"tags":[81802,81938,81942,81937,81940,81804,81939,81941],"class_list":["post-27636","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures","category-stack","tag-inorder-preorder-postorder-traversal-without-recursion-in-c","tag-iterative-inorder-traversal","tag-iterative-inorder-traversal-without-stack","tag-iterative-preorder-traversal","tag-postorder-traversal-algorithm-using-stack","tag-postorder-traversal-without-recursion-and-stack","tag-postorder-traversal-without-recursion-geeksforgeeks","tag-preorder-traversal-without-recursion-without-stack"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27636","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27636"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27636\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31284"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27636"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27636"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27636"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}