1

I implemented an algorithm for printing the postorder traversal of a binary tree iteratively. The entire algorithm works, except it goes in infinite loop when it hits the root of tree.

Can somebody point me in right direction? I've been stuck on this problem for 2 days now.

void postorder_nonrec_2(treenode *root)
{
    stack_t *s;
    stack_init(&s, 100);
    treenode *temp = root;

    while(1)
    {
        while(root)
        {
            push(s, root);
            root = root -> left;
        }

        if(stack_isEmpty(s))
            break;

        if(!top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);

            if(root == top(s) -> left)
            {
                root = top(s) -> right;
            }
            else if(root == top(s) -> right)
            {
                printf("%d ", pop(s) -> data);

                root = NULL;
            }
        }
        else
        {
            root = top(s) -> right;
        }

    }
}
7
  • IF your only termination clause is "is_empty", then show what "is_empty" does, else we can't tell...the construction is otherwise infinitely looping. Further, we would need to verify that the tree is correctly formed. A malformed tree can cause correct algorithms to loop eternally.
    – JVene
    Commented Sep 24, 2015 at 17:44
  • stack_isEmpty(stack *s) returns true if the stack is empty. Commented Sep 24, 2015 at 17:46
  • That much seems obvious, but, what if the stack is the problem? We couldn't see that from here. From what I see, the loop will continue for eternity unless that fires correctly. Put another way, have you used a debugger to see where the program is stuck looping? Is it not calling stack_isEmpty? If not, the it's probably caught in the upper loop looking for a far left node, which hints the tree itself may be the problem, but then why isn't push flooding memory (huge stack is created). If stack_isEmpty is being called, then why is it never returning true? These are the only possibilities I see
    – JVene
    Commented Sep 24, 2015 at 17:50
  • stack_isEmpty() has been tested and debugged. It has no problems. All I need is a way to figure out that the current element is the root node, and the whole tree has been traversed. Then I can pop the root node from the stack, print it and automatically it'll stop looping. Commented Sep 24, 2015 at 17:53
  • This is the function: int stack_isEmpty(stack_t *stack) { if(stack -> top == -1) return 1; return 0; } Commented Sep 24, 2015 at 17:54

2 Answers 2

1

Perhaps with the test cases you are using, there is an infinite loop at only the root, but I think the infinite loop could also occur at other places in the tree, depending on the specific tree.

The problem, I think, is that you do not correctly continue to pop up the stack when children exist on the right.

Consider the simple example where we have a root node 1 with a left child 0 and a right child 2, and suppose that 2 has a right child named 3.

In the first loop we push 1 and 0 onto the stack. Then 0 has no left child, so root becomes null. The stack is not empty, so we continue. 0 is at the top of the stack and has no right child, so we enter the first branch of the if statement. We then print out 0 and because 0 is the left child of 1 -- 1 is now the top of the stack -- the root becomes 2.

At this point we return to the top. 2 is the root and gets pushed onto the stack. 2 has no left child, so the root becomes null. The stack is not empty. 2 is at the top of the stack. It has a right child, so we enter the second branch of the if statement. This makes 3 the root.

We return to the top of the outer loop. 3 is the root and gets pushed onto the stack. 3 has no left child, so the root becomes null. The stack is not empty. 3 has no right child, so we enter the first branch of the if statement. We print out 3. Then because 3 is the right child of 2 -- 2 is at the top of the stack now -- we pop 2 off the stack, print out 2, and the root becomes null.

We return to the top of the loop. The root is already null, so nothing is pushed onto the stack. The stack is not empty. 1 is at the top of the stack. At this point the proper thing to do is to pop 1 from the stack because we have already processed its right child; however, 1 is at the top of the stack and does have a right child, so we enter the second branch of the if statement and 2 becomes the root. The situation is exactly the same as it was at the two paragraphs ago, with 1 the only element on the stack and 2 the root, so we get an infinite loop back to there.

If we changed the example so that 3 also has a right child named 4, then, if I read correctly, we would never print out 2 and would loop printing out 4 and 3.

To correct the problem, you should continue to pop the stack as long as the element you are processing is the right child of the top of the stack. I haven't compiled or tested this, but I think it would work to write something like

    if (!top(s) -> right)
    {
        root = pop(s);
        printf("%d ", root -> data);

        while (!stack_isEmpty(s) && root == top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);
        }
        if (!stack_isEmpty(s) && root == top(s) -> left)
        {
            // checking root == top(s) -> left is probably redundant,
            // since the code is structured so that root is either
            // a child of top(s) or null if the stack is not empty
            root = top(s) -> right;
        }
        else
        {
            root = NULL;
            // could actually break out of outer loop here, but
            // to be more consistent with code in the question
        }
    }
1
  • Great effort and exact solution. I put your code to work, it did like a charm. Then I cut off all the redundant pieces as suggested by you to keep the code short, and it works! Thanks! Commented Sep 27, 2015 at 17:14
0

Posting this answer to provide the full code of the solution suggested by @Evan VanderZee

void postorder_nonrec_2(treenode *root)
{
    stack_t *s;
    stack_init(&s, 100);


    while(1)
    {
        while(root)
        {
            push(s, root);
            root = root -> left;
        }

        if(stack_isEmpty(s))
            break;

        if (!top(s) -> right)
        {
            root = pop(s);
            printf("%d ", root -> data);

            while (!stack_isEmpty(s) && root == top(s) -> right)
            {
                root = pop(s);
                printf("%d ", root -> data);
            }

            root = NULL;
        }
        else
        {
            root = top(s) -> right;
        }
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.