Why my Preoder, Inorder and Postorder functions are not working

Question

#include <stdio.h>
#include <stdlib.h>

Node Creation

This structure creates the struct node data type

 struct node
    {
        int data;
        struct node *left, *right;
    } * newnode;

Create Function

create() - It first allocates the memory required for the node. When user enters the data, it recursively calls itself to create its child node, and this process goes on. When the user enters -1, it terminates the recursion and goes back from where it is called.

    struct node *create()
    {
        int x;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->left = 0;
        newnode->right = 0;
        printf("Enter data(-1 for no node)\n");
        scanf("%d", &x);
        if (x == -1)
            return 0;
        newnode->data = x;
        printf("Enter left child of %d\n", x);
        newnode->left = create();
    
        printf("Enter right child of %d\n", x);
        newnode->right = create();
        return newnode;
    }

Preorder

preorder(struct node *root) - This function displays the data of the tree in preorder manner

    void preorder(struct node *root)
    {
        if (root == 0)
            return;
    
        printf("%d\n", root->data);
        preorder(root->left);
        preorder(root->right);
    }

Inorder

inorder(struct node *root) - This function displays the data of the tree in inorder manner

    void inorder(struct node *root)
    {
        if (root == 0)
            return;
    
        inorder(root->left);
        printf("%d\n", root->data);
        inorder(root->right);
    }

Postorder

Postorder(struct node *root) - This function displays the data of the tree in postorder manner

    void postorder(struct node *root)
    {
        if (root == 0)
            return;
    
        postorder(root->left);
        postorder(root->right);
        printf("%d\n", root->data);
    }

Main Function

Main function asks the user to create a tree and then traverse it according to the choice entered by the user. The problem is that preorder, inorder and postorder are not giving the required output, and result in an infinite loop after execution.

 void main()
    {
        struct node *root;
        root = 0;
        int choice = 3, opt = 1;
    
        while (opt)
        {
            printf("Select\n 1-for creation\n 2-for preorder\n 3-for inorder\n 4-for postorder\n");
            scanf("%d", &choice);
            switch (choice)
            {
            case 1:
                root = create();
                break;
            case 2:
                printf("Preorder is: ");
                preorder(root);
                break;
            case 3:
                printf("Inorder is: ");
                inorder(root);
                break;
            case 4:
                printf("Postorder is: ");
                postorder(root);
                break;
    
            default:
                printf("Invalid choice");
                break;
            }
            printf("Wanna continue \n1-for yes\n0-for no\n");
            scanf("%d", &opt);
        }
    }

Answer 1

There is no bug with any of the traversal functions you've provided. No design or implementation problem with create () function either.

The trouble lies in the global struct node pointer newnode declared with the structure's definition.

Because each recursive call to create () is basically using the "same" newnode pointer, the tree is never really built in the way we want it to.

Let's try to dry run the create () function.

Let's say we want a tree like this:

    1
   / \
  2   3

1. create () is first called from main.

• The memory is allocated using malloc () function and the address of the memory is stored in newnode.
• Set it's attributes, left and right.
• Ask for data and put it into data attribute, if data == -1 is true, return 0.

Up until this point, this is the state:

newnode -> 1
          / \
       Null  Null

2. create () is recursively called to build the left subtree.

• The memory is allocated for newnode using malloc () and the address of the memory is stored in newnode. Note that this operation has basically "over-wrote" the address previously stored in newnode (because newnode is a global variable)

• Then again, the user will be prompted for the data and its attributes will be set.

Therefore, the tree has now become:

newnode -> 2
          / \
       Null  Null

The struct node to which newnode was previously pointing is now lost (because of loss of its address)

Similarly, when the recursive call for the right subtree is made, then, the following will be observed:

newnode -> 3
          / \
       Null  Null

Considering the same scenario for the rest of the recursive calls made, it is clear that in the end, the tree we were expecting wasn't built and the reason is the global variable newnode, the constant allocation of memory and over-writing the address in newnode led to memory leakage only.

The reason infinite recursion was found is that, during multiple recursive calls, the left or right pointer of newnode was made to point to newnode itself, leading to a cycle. This node can be found by closely tracking the data of newnode during the recursive calls.

Hence, remove the declaration of newnode pointer from the structure declaration and modify the following statement in create () function:

newnode = (struct node *)malloc(sizeof(struct node));

to this:

struct node * newnode = (struct node *)malloc(sizeof(struct node));

And

struct node
{
    int data;
    struct node *left, *right;
};

is all what's needed.

In this way, each recursive call to create () function will have its own local pointer variable newnode and there will be no overwriting, no leakage, no cycle, no infinite recursion.