C Binary Search Tree Post Order Traversal Iteratively using Stack

Question

I've spent hours trying to figure out why it wouldn't print the root node at the end.

It is unable to current = pop(&S); at the last iteration.

I can't figure out what's wrong.

Algorithm:

1.1 Create an empty stack 2.1 Do following while root is not NULL a) Push root's right child and then root to stack. b)Set root as root's left child. 2.2 Pop an item from stack and set it as root. a) If the popped item has a right child and the right child is at top of stack, then remove the right child from stack, push the root back and set root as root's right child. b) Else print root's data and set root as NULL. 2.3 Repeat steps 2.1 and 2.2 while stack is not empty.

I visualized, and drew it on a whiteboard and the logic works fine to me. However when implementing it, it crashes at the last iteration.

void postOrderIterativeS1(BSTNode *root)
{
    Stack S;
    S.top = NULL;
    BSTNode *current = root;

    int shouldContinue = 1;
    while(shouldContinue)
    {

        if(current != NULL)
        {

            if(current->right != NULL){


            push(&S, current->right);
            }

            push(&S, current);



            current = current->left;
        }
        else
        {
            current = pop(&S);
            if(peek(&S) == NULL){
                shouldContinue = 0;
            }
            if(current->right != NULL && peek(&S)->item == current->right->item)
            {
                pop(&S);
                push(&S,current);
                current = current->right;
            }

            else


            {

                int items= current->item;
                printf("%d ", current->item);
                current = NULL;
            }

        }

    }
}

If you want the full code, https://pastebin.com/z4rPebrJ

Exeuction:

There is no break condition in that infinite loop. No `return`, and no `break`. The value `1` will always be true, and eventually you're *probably* popping an empty stack. — WhozCraig, Sep 22 '20 at 09:01
If you run thgis with a debugger, you'll probably understand what's going wrong. — Jabberwocky, Sep 22 '20 at 09:02
@Jabberwocky yeah I tried using the debugger and watch it, but I don't know why the Stack at last iteration is empty, hence crashing the program.. — dikolav150, Sep 22 '20 at 11:41

score 1 · Accepted Answer · answered Sep 22 '20 at 11:50

1

There is at least a problem here:

  current = pop(&S);
  if (peek(&S) == NULL) {
    shouldContinue = 0; 
    // peek(&S) is NULL here 
    // but in the if below you dereference peek(&S) which is NULL
    // and therefore you get a crash
  }
  if (current->right != NULL && peek(&S)->item == current->right->item)
  {
    pop(&S);
    push(&S, current);
    current = current->right;
  }

Just change this:

if (current->right != NULL && peek(&S)->item == current->right->item)

to this:

if (shouldContinue && current->right != NULL && peek(&S)->item == current->right->item)

answered Sep 22 '20 at 11:50

Jabberwocky

48,281
17
65
115

Thank you!! I did not see that. Does this mean, the moment shouldContinue is 0, in that if statement, it won't bother executing && peek(&S)->item == current->right->item ? – dikolav150 Sep 22 '20 at 12:15
Yes it does mean that: For more information read [this](https://stackoverflow.com/a/45848954/898348) about the `&&` and the `||` operators. – Jabberwocky Sep 22 '20 at 12:18

C Binary Search Tree Post Order Traversal Iteratively using Stack

1 Answers1