Binary tree traversal Inorder output is wrong why?

user_14795252 0
Viewed 130

Can someone explain why my output is wrong and how to fix it?

for example: i will input A B C D E

output is giving me A B C D E

insead of Inorder Traversal: D B E A C

this is my code:

int main()
{
struct node *root = NULL;
int choice, n;  // item
char item;
do
{

    printf("\n1. Insert Node"); 
    printf("\n2. Traverse in Inorder");

    printf("\nEnter Choice : ");
    scanf("%d",&choice);

    switch(choice)
    {
    case 1:
        root = NULL;
        printf("\n\n Nodes : ");
        scanf("%d",&n);
        
        for(int i = 1; i <= n; i++)
        {
            printf("\nEnter data for node %d : ", i);
            scanf(" %c",&item);
            root = Create(root,item);
        }
        break;
        
    case 2:
        printf("\nBST Traversal in INORDER \n");
        Inorder(root); break;
  
    default:
        printf("\n\nINVALID OPTION  TRY AGAIN\n\n"); break;
    }
} while(choice != 3);

}

struct node *Create(struct node *root, char item)
{
if(root == NULL)
{
    root = (struct node *)malloc(sizeof(struct node));
    root->left = root->right = NULL;
    root->data = item;
    return root;
}
else
{
    if(item < root->data )
        root->left = Create(root->left,item);
    else if(item > root->data )
        root->right = Create(root->right,item);
    else
        printf(" Duplicate Element !! Not Allowed !!!");

    return(root);
}
}

void Inorder(struct node *root)
{
if( root != NULL)
{
    Inorder(root->left);
    printf(" %c ",root->data);
    Inorder(root->right);
}
}

i doubled check the algorithm of The traversal Inorder but my output is still wrong i don't understand why? did i miss something here

inorder tree linked-list
1 Answers

The result is as expected. The in-order traversal should not produce D B E A C for your input of A B C D E

This is how the tree is constructed.

First the root is created with value A

Then B is inserted. As B > A, it is inserted as a right child of the root:

    A
     \
      B

Then B is inserted. As C > A, it is inserted in the right subtree. There again we find C > B, so the new node will be inserted as a right child of B:

    A
     \
      B
       \
        C

In the same way D and then E are inserted, giving this tree:

    A
     \
      B
       \
        C 
         \
          D
           \
            E

Note that this tree is not balanced at all. That's what happens when you insert nodes in their lexical order. If you would insert them in a more random order, we would expect the tree to be more balanced.

But it does not actually matter for the in-order traversal. What you have implemented is a binary search tree (BST). And one important property of BSTs is that their in-order traversal always produces the data in their right order. And so irrespective of the order in which you input the letters A B C D and E, the in-order traversal should always output this sequence:

 A B C D E

This is correct.

user_54598390
Related