Recursive Binary Tree Traversal Code Goes to Infinity

Question

I am trying to traverse a binary tree built with the input data from keyboard. Data is inserted to the binary tree successfully. I have a switch statement, where 'case 2' should traverse (and print) the binary tree with Inorder, Preorder and Postorder traversal algorithms using recursion respectively. However when 'case 2' is called, only the first data that should be printed regarding Inorder traversal is printed on screen; and it is also printed many times (infinite) where I need to stop the compiling operation. I would be more than happy if someone help me out with this one.

(RootPtr is the top -Level 0- node of the binary tree defined globally; and GetNode is basically an initializer function (using malloc) for type TreePtr pointers.)

Thank you all in advance.

This is the struct definition;

  typedef struct treeItem
{
    int data;
    struct treeItem *left;
    struct treeItem *right;

}Tree , *TreePtr;

These three are the traversing functions called respectively;

void inorder (TreePtr TemPtr)
{

    while(TemPtr != NULL)
    {
        inorder((*TemPtr).left);
        printf(" %d ", (*TemPtr).data);
        inorder((*TemPtr).right);
    }
    printf("\n");
}

void preorder (TreePtr TemPtr)
{
    while(TemPtr != NULL)
    {
        printf(" %d ", (*TemPtr).data);
        preorder((*TemPtr).left);
        preorder((*TemPtr).right);
    }
    printf("\n");
}

void postorder (TreePtr TemPtr)
{
    while(TemPtr != NULL)
    {
        postorder((*TemPtr).left);
        postorder((*TemPtr).right);
        printf(" %d", (*TemPtr).data);
    }
    printf("\n");
}

This one is the related 'case' of the switch statement;

  case 2:
            TreePtr LocPtr;
            GetNode(&LocPtr);
            LocPtr = RootPtr;

            printf("\n");
            printf("Inorder traversal:");
            inorder(LocPtr);
            printf("Preorder traversal:");
            preorder(LocPtr);
            printf("Postorder traversal:");
            postorder(LocPtr);
            printf("\n");

            break;

jonathanGB jonathanGB · Accepted Answer · 2016-01-10T19:59:58

There shouldn't be a while loop inside your traversal functions. Recursivity will go in all nodes already.

void inorder (TreePtr TemPtr)
{
    if (TemPtr != NULL) {
        inorder((*TemPtr).left);
        printf(" %d ", (*TemPtr).data);
        inorder((*TemPtr).right);
    }

    printf("\n");
}

If you think about it, your TemPtr parameter isn't changing to NULL when you iterate in the loop. It would therefore be stuck in an infinite loop.

Explanation on tree traversal:

In your main, case 2, you call inorder with the root of the tree as parameter. Then we need to traverse the tree.

inorder(LocPtr);

In-order traversal is:

go to left child ... visit current node ... go to right child

We need two things in a recursive function/method: a base case, and a recursive call.

Here, our base case is if (TemPtr != NULL). When this condition is false, we know we have reached a leaf. If TemPtr indeed is a leaf, we don't go further to its children (which would throw errors).

But if TemPtr is not NULL, it means we are currently at a valid node. We must therefore follow the definition of in-order traversal (as stated previously).

We visit the left child:

inorder((*TemPtr).left); // equivalent to inorder(TemPtr->left);

we visit the current node:

printf(" %d ", (*TemPtr).data); // equivalent to printf (" %d ", TemPtr->data);

and we visit the right child:

inorder((*TemPtr).right); // equivalent to inorder(TemPtr->right);

When inorder is finished, the caller of inorder continues where it was. This process continues until inorder(LocPtr) finishes, and at this point you'll be back into the main, and your whole tree will have been traversed in-ordered.

The easiest way to visualize this is to draw the calls on a sheet of paper. Functions will stack on each other (main on the bottom), and are removed from the stack once they're finished.

Recursive Binary Tree Traversal Code Goes to Infinity

1 Answers