algorithm - Making a void toBST function in C which takes 2 arguments : Tree* root and an array and adds all tree nodes to an array - order does not matter

Question

I am trying to implement the following function in C :

void BSTtoArr(Tree * root,Tree* arr[]) 

which takes a tree and add its nodes into an array of nodes. What I ve written so far was :

void BSTtoArr(Tree * root,Tree* arr[]) {
    static int pos = 0;
    if(root == NULL) return;
    BSTtoArr(root->left,arr);
    v[pos++] = root->data;
    BSTtoArr(root->right,arr);
}

I also tried

void BSTtoArr(Tree * root,Tree* arr[],int i) {
    if(root == NULL) return;
    BSTtoArr(root->left,arr,i+1);
    v[i] = root->data;
    BSTtoArr(root->right,arr,i+1);

}

However I can not get the values added , when I am trying to call the function

Tree* arr = (Tree*) malloc(TreeSize(root) * sizeof(Tree));
BSTtoArray(root,&arr); 

The values are not added properly. Can you help me with an implementation for this function?

Answer 1

The first problem is here:

Tree* arr = (Tree*) malloc(TreeSize(root) * sizeof(Tree));

This gives you "an array" of Tree elements but what you want is "an array" of pointers to Tree elements.

So change it to:

Tree** arr = malloc(TreeSize(root) * sizeof *arr);

The second problem is here:

void BSTtoArr(Tree * root,Tree* arr[],int i) {
    if(root == NULL) return;
    BSTtoArr(root->left,arr,i+1);  <---- i+1
    v[i] = root->data;             <---- data ???
    BSTtoArr(root->right,arr,i+1); <---- i+1

}

You pass the same array index to the left and the right recursion so the recursive calls will write to the same index. You need to make sure that every time you write to the array, it's done with a new index value. To do that you can pass a pointer to the index variable and update the index when a new element is inserted in the array.

Further, you to try to save root->data into the array but the array is supposed to hold the nodes - not the node data.

To solve this you can do:

void BSTtoArr(Tree * root, Tree* arr[], int* i) {
    if(root == NULL) return;
    BSTtoArr(root->left, arr, i);
    v[*i] = root;
    *i = *i + 1;
    BSTtoArr(root->right, arr, i);

}

and call it like:

Tree** arr = malloc(TreeSize(root) * sizeof *arr);
int i = 0;
BSTtoArray(root, arr, &i);