2
\$\begingroup\$

How could I optimize this binary search tree?

#include<stdio.h>
#include<stdlib.h>
struct NODE
{
    int info;
    struct NODE *right;
    struct NODE *left;
    struct NODE *parent;
};
typedef struct NODE node;

node *createnode(node *temp,int number)
{
    temp=(node*)malloc(sizeof(node));
    temp->info=number;
    temp->right=NULL;
    temp->left=NULL;
    temp->parent=NULL;
return temp;
}

node *insert(node *head,int number)
{
    node *temp;
    temp=createnode(temp,number);
    node *traverse=head;
    if(head==NULL)
    {
        head=temp;
        temp->parent=NULL;
        return head;
    }
    else
    {
        while(traverse!=NULL)
        {
            if(number < traverse->info)
            {
                if(traverse->left==NULL)
                {
                    traverse->left=temp;
                    temp->parent=traverse;
                    break;
                }
                traverse=traverse->left;
            }
            else if(number>traverse->info)
            {
                if(traverse->right==NULL)
                {
                    traverse->right=temp;
                    temp->parent=traverse;
                    break;
                }
                traverse=traverse->right;
            }
            else
                break;
        }
    }
return head;
}

node *find(node *head,int number)               // finding the position of the element which we want to delete
{
    node *traverse=head;
    if(traverse==NULL)
        return NULL;
    else
    {
        while(traverse!=NULL)
        {
            if(number<traverse->info)
            {
                if(traverse->left==NULL)
                {
                    printf("Number not found\n");
                    return NULL;
                }
                traverse=traverse->left;
            }
            else if(number>traverse->info)
            {
                if(traverse->right==NULL)
                {
                    printf("Number not found\n");
                    return NULL;
                }
                traverse=traverse->right;
            }
            else
                break;
        }
    }
return traverse;
}
int find_children(node *temp)                   // finding the number of children of the the node that we want to delete
{
    int count=0;
    if(temp->left!=NULL)
        count+=1;
    if(temp->right!=NULL)
        count+=1;
return count;
}
node *delete(node *head,int number)               //deleting the node
{
    int children;
    node *temp=head;
    temp=find(temp,number);
    if(temp==NULL)
        return head;
    else if(head->left==NULL && head->right==NULL)
        return NULL;
    else
    {
        children=find_children(temp);
        if(children==0)
        {
            if(temp->parent->left==temp)
            {
                temp->parent->left=NULL;
            }
            else if(temp->parent->right==temp)
            {
                temp->parent->right=NULL;
            }
        }
        if(children==1)
        {
            if(temp->parent==NULL)
            {
                if(temp->right!=NULL)
                {
                    temp->right->parent=NULL;
                    head=temp->right;
                }
                else if(temp->left!=NULL)
                {
                    temp->left->parent=NULL;
                    head=temp->left;
                }
            }
            else
            {
                if(temp->parent->left==temp)
                {
                    if(temp->right!=NULL)
                    {
                        temp->right->parent=temp->parent;
                        temp->parent->left=temp->right;
                    }
                    else if(temp->left!=NULL)
                    {
                        temp->left->parent=temp->parent;
                        temp->parent->left=temp->left;
                    }
                }
                if(temp->parent->right==temp)
                {
                    if(temp->right!=NULL)
                    {
                        temp->right->parent=temp->parent;
                        temp->parent->right=temp->right;
                    }
                    else if(temp->left!=NULL)
                    {
                        temp->left->parent=temp->parent;
                        temp->parent->right=temp->left;
                    }
                }
            }
        }
        if(children==2)
        {
            node *temp1;
            node *temp2;
            temp1=temp;
            temp2=temp->right;
            while(temp2->left!=NULL)
            {
                temp1=temp2;
                temp2=temp2->left;
            }
            temp->info=temp2->info;
            if(temp1->left==temp2)
            {
                    temp1->left=temp2->left;
            }
            else
            {
                temp1->right=temp2->right;
            }
        }

    }
return head;
}
void printing(node *head)
{
    if(head==NULL)
        return ;
    printing(head->left);
       printf("%d ",head->info);
    printing(head->right);
}

int main()
{
    node *head;
    int number,choice;
    printf("Choose one of the option\n");
    while(1)
    {
        printf("\n1.Enter a element\n2.Delete an element\n3.print tree\n4.Exit\n");
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:
            {
                scanf("%d",&number);
                head=insert(head,number);
                break;
            }
            case 2:
            {
                scanf("%d",&number);
                head=delete(head,number);
                break;
            }
            case 3:
            {
                printing(head);
                break;
            }

            case 4:
            {
                exit(0);
                break;
            }
        }
    }
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! To help reviewers give you better answers, please add sufficient context to your question. The more you tell us about what your code does and what the purpose of doing that is, the easier it will be for reviewers to help you. See also this meta question. \$\endgroup\$ – SuperBiasedMan Oct 10 '15 at 17:01
2
\$\begingroup\$

How could I optimize this binary search tree?

Higher-level suggestions:

  • Forward declaration of the supported operations would be nice, so I can see them at a glance without scrolling through the entire post
  • Given the current supported operations, NODE doesn't really need the parent. You could refactor and simplify without it
  • In insert, you first create allocate a node, but it might not be used if the value already exists in the tree
  • A naming convention for types would be good. node, in particular, is commonly used as variable name when working with trees, so it's confusing that it's actually a type
  • find_children is poorly named. count_children would be better

Lower-level suggestions:

  • temp is a poor name. Everywhere you used temp, node would have been better (unfortunately it was taken as a type name, as mentioned earlier)
  • Instead of info a more common name to use for the data in a tree node is, well, data
  • In many places you have if (condition) { return ...; } else { ...; }. When the if part returns, the else statement can be eliminated, which would often let you reduce the indent level of the rest of the routine, making it more readable
  • return 0 is unnecessary in main, the compiler adds that automatically
  • It's really odd to unindent the return statements. Usually it's at the same indent level as the body of the routine
  • It's more readable to put spaces around operators, for example temp->left = NULL instead of temp->left=NULL, and if (head == NULL) instead of if(head==NULL), and if (number > traverse->info) instead of if(number>traverse->info)

The logic in most of the routines can be simplified. For example, consider this snippet in find:

node *traverse=head;
if(traverse==NULL)
    return NULL;
else
{
    while(traverse!=NULL)
    {
        // ...
    }
}
return traverse;

Could be simplified as this, without even knowing what's inside that while:

node *traverse = head;
while (traverse != NULL)
{
    // ...
}
return traverse;

Going further, the implementation of the routine can be reduced to a much more simplified form:

node *traverse = head;
while (traverse != NULL)
{
    if (number < traverse->info)
    {
        traverse = traverse->left;
    }
    else if (number > traverse->info)
    {
        traverse = traverse->right;
    }
    else
    {
        return traverse;
    }
}
printf("Number not found\n");
return NULL;

If you look closely, the other routines can be simplified as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.