I have a binary search tree and I want to copy the nodes to an array with inorder (recursive function).

Question

Hi I have a BST binary search tree

typedef struct Treenode *SearchTree;
struct  Treenode
{
    int Element;
    SearchTree Left;
    SearchTree Right;
};

and I want to create a function

FillArray(int sizeoftree, tree, int array[])

And I want to use an array and copy the nodes of the tree in the array. How can I do this? the following code does not work. I tried:

int FillArray(int a,SearchTree T,int arr[])
{
    if (T==NULL) 
    {   
       return 0; 
    }
    else
    { 
       FillArray(a,T->Left,arr);   
       arr[a]=T->Element;
       a++; 
       FillArray(a,T->Right,arr);
    } 
}

Answer 1

Your problem is that your function FillArray is only modifying its argument a, which is not visible to its caller, since argument passing in C is by value. You will need some way to have the recursive calls tell the spot in arr to which to add the elements. One simple way to do this would be to add a parameter, say, index that gives the first index in arr to which to add an element, and return from FillArray the number of elements added so that you can properly update index after calling FillArray recursively and to return the total number of elements added.

Answer 2

FillArray is declared as returning an int, but you do not have a return value in the else case.

You can use this return value to denote the number of elements filled in; this way, you know where to place the current element in-order.

int FillArray(int a, SearchTree T, int arr[]) {
    int count = 0;

    if (T) {
        count += FillArray(a, T->Left, arr);
        arr[a + count++] = T->Element;
        count += FillArray(a + count, T->Right, arr);
    }

    return count;
}

Answer 3

gotta pass a by reference