data-structurestreebinary-treetree-traversalpostorder

Postorder Traversal of Tree iterative method


I am trying to implement postorder traversal of tree using 2 stacks using iterative method. I have implementated the right algorithm. But still didn't getting output, getting error as, Segmentation fault (core dumped). Where I have done wrong can anyone tell me ?

void postorder_iterative(struct node *root)
{
    struct node *stack1[15],*stack2[15];
    int top1=-1,top2 =-1;
    root = stack1[++top1];

    while(top1>=0)
    {
        root = stack1[top1--];
        stack2[++top2] =root;
        if(root->left != NULL)
            stack1[++top1] = root->left;
        if(root->right != NULL)
            stack1[++top1] = root->right;

    }
    while(top2>=0)
        printf("%c\t",stack2[top2--]->data);
}

Solution

  • You are reading an undefined value with this statement, in the first iteration of the loop:

    root = stack1[top1--];
    

    This first stack element is undefined, because you never initialised it. It was supposed to get initialised here:

    root = stack1[++top1];
    

    But this does not put anything in the stack. Instead it overwrites root with an undefined value.

    It should have been the reversed:

    stack1[++top1] = root;
    

    This fixes the issue.

    Don't forget to print a new line character once you have printed the list, so nothing is pending in the buffer.