1

Here's my code. Please let me know the bug.The question is to convert a given ordered linked list into a binary search tree.

Thanks.

struct treenode* makeBSTnode(struct node* head)
{
    struct treenode *root=(struct treenode*)malloc(sizeof(struct treenode));
    root->data = head->data;
    root->leftchild = NULL;
    root->rightchild = NULL;
    return root;
}


struct treenode* makeBST(struct node **head,int iterations)
{
    if(iterations==0)
    {
        /*this is the code for the base condition*/    
        struct treenode *root=(struct treenode*)malloc(sizeof(struct treenode));
        root = makeBSTnode(*head);
        return root;
    }
    else
    {
        /*this is for the case when the node is not single but should be broken down into parts*/
        struct node *leftchildnode=NULL,*rightchildnode=NULL,*rootnode=NULL,*temp;
        temp = (struct node*)malloc(sizeof(struct node));
        struct treenode *root = (struct treenode*)malloc(sizeof(struct treenode)); 
        int limit = (int)ceil((float)(3*iterations)/2);
        for(int i=1;i<=limit;i++)
        {
            if(i==(int)ceil((float)iterations/2))
            {
                leftchildnode = (struct node*)malloc(sizeof(struct node));
                leftchildnode = *head;
            }
            else if(i==iterations)
            {
                rootnode = (struct node*)malloc(sizeof(struct node));
                rootnode = *head;
            }
            else if(i==(int)ceil((float)(3*iterations)/2))
            {
                rightchildnode = (struct node*)malloc(sizeof(struct node));
                rightchildnode = *head;
            }
            if(*head)
            (*head) = (*head)->next;
            else
            break;
        }
        root = makeBSTnode(rootnode);
        root->leftchild = makeBST(&temp,(int)ceil((float)iterations/2));
        root->rightchild = makeBST(&rootnode,(int)ceil((float)(3*iterations/2)));
        return root;
    }
}

I called this makeBST function in main as: root = makeBST(&head,(int)ceil((float)length/2));

AstroCB
  • 12,337
  • 20
  • 57
  • 73
Aspirant9
  • 163
  • 1
  • 13
  • [Please don't cast the return value of `malloc()` in C](http://stackoverflow.com/a/605858/28169). – unwind Sep 25 '13 at 16:24
  • Does this return an invalid tree or does this crash? Bug report? Have you tried debugging at all? – dckuehn Sep 25 '13 at 16:19
  • @dckuehn - the program breaks at the point (*head) = (*head)->next; – Aspirant9 Sep 25 '13 at 16:37
  • @unwind - can you please elaborate a bit more? Cause the program doesn't break or crash due to malloc. – Aspirant9 Sep 25 '13 at 16:41
  • @Aspirant9 The tl;dr is that the cast is not required, and by casting, you could be hiding a number of logic errors. – Dennis Meng Sep 25 '13 at 16:49
  • "the program doesn't break or crash due to malloc" - Then why *does* it crash? As-posted this doesn't even *compile*. You already identified the suspected problem. So what is stopping you from *fixing it* ? – WhozCraig Sep 25 '13 at 17:44
  • I think this question belongs to http://codereview.stackexchange.com/ – Farouq Jouti Sep 25 '13 at 18:07

0 Answers0