Convert Sorted Array to Binary Search Tree in c

Question

I want to convert sorted 1-D array to Binary Search Tree, but I am not getting the desired output with this code:

int arr[7] = {-10,-3,-1,0,3,7,9};

typedef struct tree{
   int data;
   struct tree *left;
   struct tree *right;
}bst;

struct tree *CreateNode(int data){
   bst *node = (bst*)malloc(sizeof(bst));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return node;
}
struct tree *BST(bst *root,int start,int end){
    if(start>end){
        return NULL;
    }
    int mid = start + (end-start)/2;
    root = CreateNode(arr[mid]);
    BST(root->left,start,mid-1);
    // printf("%d\n",root->data);
    BST(root->right,mid+1,end);
    return root;
 }

So much information is missing from this question. And then there's the fact that two sentences you did include seem to talk about completely different things. You have failed to communicate what you are attempting to do and to demonstrate the problem you are facing. — ikegami
– ikegami, Commented Aug 9, 2022 at 18:18
1) Create an insert function. 2) Call it for every element in the list. — klutt
– klutt, Commented Aug 9, 2022 at 18:25
@ikegami I want to convert sorted 1-D array to binary search tree — Jitraj Swargiari
– Jitraj Swargiari, Commented Aug 9, 2022 at 18:26
That's neither of the things the question states! Fix your question — ikegami
– ikegami, Commented Aug 9, 2022 at 18:28

David Ranieri · Accepted Answer · 2022-08-10 07:10:45Z

1

You need to pass a reference to the pointer, otherwise you alter the value of a local pointer, this should work:

struct tree *BST(bst **root,int start,int end){
    if(start>end){
        return NULL;
    }
    int mid = start + (end-start)/2;
    *root = CreateNode(arr[mid]);
    BST(&((*root)->left),start,mid-1);
    //printf("%d\n",(*root)->data);
    BST(&((*root)->right),mid+1,end);
    return *root;
}

or as pointed out by @JohBollinger, instead of passing a pointer to the node, use the return value of the recursive function to fill the nodes:

struct tree *BST(int start,int end){
    if(start>end){
        return NULL;
    }
    int mid = start + (end-start)/2;
    bst *root = CreateNode(arr[mid]);
    root->left = BST(start,mid-1);
    //printf("%d\n",root->data);
    root->right = BST(mid+1,end);
    return root;
}

edited Aug 10, 2022 at 7:10

answered Aug 9, 2022 at 18:35

David Ranieri

41.2k8 gold badges58 silver badges103 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

John Bollinger Over a year ago

Or they could use the return value of their current function, which they presently ignore. In which case they wouldn't need the root argument. I think that would probably be a better choice for them.

David Ranieri Over a year ago

@JohnBollinger good point ;) edited

Collectives™ on Stack Overflow

Convert Sorted Array to Binary Search Tree in c

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related