Where is the bug in this search code for a binary search tree?

Question

I have written this code for strict Binary Search trees. (If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N – 1 nodes.) Unfortunately, it's not printing values correctly. I don't know what's the problem. I have seen other sites on the internet and the code is nearly same but still, I can't find a bug in my code.

#include <stdio.h>
#include <stdlib.h>
struct node
{
    struct node* prev;
    int data;
    struct node* next;
};
void Binary_Search_Tree(struct node *newnode,struct node *p);
void print(struct node* p);

main()
{
    struct node *root,*nnode,*temp;
    int c,d;
    root=malloc(sizeof(struct node));

    printf("Enter the root data\t");
    scanf("%d",&d);
    root->data=d;
    root->prev=NULL;
    root->next=NULL;

    while(1)
    {
        printf("Enter your choice\n1 insert element.\n2 print tree.\n3 Exit");
        scanf("%d",&c);
        switch(c)
        {
            case 1:
                nnode=malloc(sizeof(struct node));
                printf("Enter the node data\t");
                scanf("%d",&d);

                nnode->data=d;
                nnode->prev=NULL;
                nnode->next=NULL;
                temp=root;

                Binary_Search_Tree(nnode,temp);
                break;
            case 2:
                temp=root;
                print(temp);
                break;
            case 3:
                free(root);
                free(nnode);
                free(temp);
                temp=nnode=root=NULL;
                exit(1);
                break;
        }
    }
    return 0;
}

void Binary_Search_Tree(struct node *newnode,struct node *p)
{

    if(newnode->data<p->data)
    {
        if(p->prev=NULL)
        {
            p->prev=newnode;
        }
        else if(p->prev!=NULL)
        {
            p=p->prev;
            Binary_Search_Tree(newnode,p);
        }
    }
    else if(newnode->data>p->data)
    {
        if(p->next=NULL)
        {
            p->next=newnode;
        }
        else if(p->next!=NULL)
        {
            p=p->next;
            Binary_Search_Tree(newnode,p);
        }
    }
}

void print(struct node* p)
{
    if(p!=NULL)
    {
        print(p->prev);
        printf("%d\n",p->data);
        print(p->next);
    }
}

Answer 1

The major problem is you have used assignment in place of equality.

if( p->next=NULL )

does completely differently than what you expected it to be. It would be

if ( p->next == NULL )
             ^^^

Same for the p->prev the check would be p->prev == NULL.

So let's analyze the first case where you made the error.

if( p->next = NULL )

first assigns NULL to the p->next and then we know the result of assignment statement is the value assigned. So the conditional would be

 if( NULL ) 

So the if statement is never entered. So is else because then p->next = NULL. So it doesn't add the new node. Tree remains unchanged.

It didn't stop here. As you lost the address of the newly allocated node - you have memory leak here.

Then comes the solution

if( p->next == NULL )

Well when we reach a leaf level it would be equal to NULL and then you assign to it the address of newly allocated node. That solves the problem.

Few things -

1. Check the return value of malloc. In case it fails it would return NULL. ₁

   root=malloc(sizeof(struct node));
   if( root == NULL ){
      perror("Malloc failure");
      exit(EXIT_FAILURE);
   }
   

2. Free the dynamically allocated memory when you are done working with it.

   void freeTree(struct node *root){
      if( root ){
         freeTree(root->prev);
         freeTree(root->next);
         free(root);
      }
   }
   

3. Enable compiler warnings -Wall -Werror. If you did that compiler would have clearly shown you the problem.

   error: suggest parentheses around assignment used as truth value [-Werror=parentheses]
            if(p->next=NULL)
            ^~
   

4. Well another thing check the return value of scanf.

   if( scanf("%d",&d) != 1 ){
     // Input failed 
     exit(EXIT_FAILURE); // or handle error.
   }
   

5. As mentioned in comment by Jonathan Leffler, readablility will improve if you write the statement properly spaced. else if(newnode->data>p->data) is hard to read. Compared to that else if (newnode->data > p->data) is much more readable. The error would be readily visible to your eye when you write the statement if(p->next = NULL). The obvious one would be if(p->next == NULL).

---

Freeing the tree is a bit tricky in that you will have to always perform post order traversal. You need to free the children first then you would go for freeing the parent. Otherwise there will be memory leak.

_{1. Earlier I mentioned fprintf(stderr,...) Basile Starynkevitch to use perror which is a good choice for printing diagnostic error messages.}