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
}
}
stack_isEmpty(stack *s)
returns true if the stack is empty.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.int stack_isEmpty(stack_t *stack) { if(stack -> top == -1) return 1; return 0; }