CODEWITHSUNDEEP
cdata-structuresbinary-search-tree
Jitraj Swargiari
Jitraj Swargiari

Reputation: 7

Convert Sorted Array to Binary Search Tree in c

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

Upvotes: 0

Views: 318

Answers (1)

David Ranieri
David Ranieri

Reputation: 41017

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

Upvotes: 1

Related Questions