Flattening a binary search tree into a list

Question

typedef struct node *blah;

int *breath_search(struct node *root){

    int *numbers = calloc(20,sizeof(*numbers)); int listpointer = 0;
    struct node **currentlist = calloc(20,sizeof(struct node*));
    struct node **updatedlist = calloc(20,sizeof(struct node*));
    currentlist[0] = root;
    int iterations = 1;

    int depths = 3;
    while(depths){


        int i = 0; int j;
        for(j=0;j<iterations;j++){
            if(currentlist[j] == NULL){
                updatedlist[i] = NULL; i++;
                updatedlist[i] = NULL; i++;
                numbers[listpointer] = 0; listpointer++;
            }
            else if(currentlist[j] != NULL){
                updatedlist[i] = currentlist[j]->left; i++;
                updatedlist[i] = currentlist[j]->right; i++;
                numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key); listpointer++;
            }
        }

        currentlist = updatedlist;
        updatedlist = (blah[])     {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};
        iterations = iterations*2;

        depths--;

    }

    return numbers;
}

I've been looking at this code for hours and it doesn't make sense why it doesn't work. I intend to give the function a node and it would return back to me a pointer a list containing all the numbers in the binary tree.

My binary tree is like

        231
     /      \
    82      247
   /  \     /  \
  80  137 NULL 263

My function only returns back a pointer to list

231,82,247,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

I expected

231,82,247,80,137,0,263,0,0,0,0,0,0...

Answer 1

I believe that the error in your code is the line ::

updatedlist = (blah[]) {NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL,NULL};

which I doubt is a valid syntax. Since, you are trying to allocate a new array where you can save the children of the node you just visited, it would be advisable to calloc a new array, which you can then use in your code.

So, the line mentioned above shall be change to this ::

updatedlist = calloc(20,sizeof(struct node*));

A few points which you shall take in consideration, while allocating so much memory is, to free the memory which is no longer of use, since C does not do that explicitly for you, you need to take care of that yourself, so as to avoid any memory leaks. Since, after every iteration of the while loop, the currentList is useless, you shall add a statement (before assigning updatedList to currentList)

free(currentList);

And at the end of the program freeing the updatedList as well.

Secondly, what you are currently doing is something like the level-order traversal of the binary tree. So, you can possibly try using an STL queue, and there would be no need to create and swap arrays like you are doing. Something like this ::

int *breath_search(struct node *root){

    int *numbers = calloc(20,sizeof(*numbers));
    int listpointer = 0;
    queue<node*> q;
    q.push(root);
    int iterations = 1;

    int depths = 3;
    while(depths){
        int i = 0, j;
        for(j=0; j<iterations; j++){
            node* currentNode = q.pop();
            if(currentNode == NULL){
                q.push(NULL);
                q.push(NULL);
                numbers[listpointer] = 0;
                listpointer++;
            }
            else if(currentNode != NULL){
                q.push(currentNode->left);
                q.push(currentNode->right);
                numbers[listpointer] = (int) alpabatise(currentlist[j]->newitem.key);
                listpointer++;
            }
        }
        iterations = iterations*2;
        depths--;
    }
    return numbers;
}

I believe this would be a much better approach to do it, since you do not have to keep on allocating and freeing memory, so it lessens that overhead. I used STL queue, you can definitely use your own queue.