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);
    }
}

"printing values correctly" - please specify expected and actual values — Antti Haapala
You should show some sample inputs, and the actual and expected output (ir's an important part of creating an MCVE — minimal reproducible example). It isn't clear how you ensure a strictly binary tree when you add one node at a time. Don't you need to add 1, then 2, then 4, then 8 nodes? — Jonathan Leffler
Well I added 2 characters and that solved the problem ... if(p->prev=NULL)-->if(p->prev==NULL) and p->next=NULL--> p->next==NULL — user2736738
It would be so much easier to read the code if you put spaces around binary operators. Reading else if(newnode->data>p->data) instead of else if (newnode->data > p->data) is harder; it takes more effort to find the tokens, especially when the arrows and the > are in sequence. It also makes it easier to spot that if(p->next=NULL) is wrong if you write if(p->next = NULL); it's more obvious that it should be if(p->next == NULL). — Jonathan Leffler
Next time, compile with all warnings and debug info: gcc -Wall -Wextra -g with GCC. Improve the code to get no warnings. Use the debugger gdb — Basile Starynkevitch

user2736738 user2736738 · Accepted Answer · 2017-12-24T07:18:24

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 -

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);
}

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);
   }
}

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)
         ^~

Well another thing check the return value of scanf.

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

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.}

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

1 Answers