Binary Tree to Array: Wrong values inserted into Array

Question

I have no Idea what I'm doing wrong. I have 3 functions to store the data from two binary trees into arrays. My Problem is the following: Everything works fine for arr2 but not for arr1. Does anybody have an idea how to resolve this? Help would be appreciated!

EDIT: The first array looks like it's also containing the values from arr2 and some random numbers.

The first function creates the arrays and calls treeToArray.

void merge(Node* n1, Node* n2){
    int l1 = getTreeSize(n1);   
    cout << "array size " << l1 << endl;
    int *arr1 = new int[l1];   
    int i = 0;
    treeToArray(n1, arr1, i);  //This array is not filled how it's supposed to be. 

    int l2 = getTreeSize(n2);
    cout << "array size " << l2 << endl;
    int *arr2 = new int[l2]; //corrected this, thanks!
    int j = 0;
    treeToArray(n2, arr2, j);

    for(int i = 0; i < l1; ++i)
        cout << "array" << arr1[i] << " ";

    merge(arr1, arr2, l1, l2);

}

treeToArray is supposed to store the Tree's data into the array.

void treeToArray(Node* n, int values[], int index) {
     if(n == NULL)
          return;

     if(n->left != NULL)
          treeToArray(n->left, values, index);

     cout << "speichere " << n->data << endl;
     values[index] = n->data;
     index++;

     if(n->right != NULL)
          treeToArray(n->right, values, index);

 }

And getTreeSize returns the size of the Tree.

 int getTreeSize(Node* n) {
      if(n == NULL) {
           return 0;
      } else {
           return (getTreeSize(n->left) + getTreeSize(n->right) + 1 ); //
      }
 }

Are you sure you want int *arr2 = new int[3]; in the merge function? — pkacprzak
– pkacprzak, Commented Feb 28, 2014 at 19:09
Thanks!! It has to be l2, which is the size of n2. But the problem is not resolved. — tyso89
– tyso89, Commented Feb 28, 2014 at 19:11
Sorry. I mean what is the value of n1 and n2? Since you did the same operations of the two parameters, there must be some difference between these two parameters. And in treeToArray(), the index of left node will be the same as current node. That might be the reason. — Steve
– Steve, Commented Feb 28, 2014 at 19:35

Useless · Accepted Answer · 2014-02-28 19:53:38Z

Your treeToArray function takes an integer index by value, which means there is no communication between different calls.

I've annotated the code with the actual values of index in the first call, but you can step through in a debugger to confirm this if you want to follow the recursion.

void treeToArray(Node* n, int values[], int index) {
     // start first call with index = 0
     if(n == NULL)
          return;
     if(n->left != NULL)
          treeToArray(n->left, values, index);
     // we passed 0 to the left subtree call, and get nothing back
     // so index is still 0 here

     values[index] = n->data;
     // we just overwrote the left subtree's first element with our data
     index++;

     if(n->right != NULL)
          treeToArray(n->right, values, index);
     // the right subtree now always starts from 1 ...
}

If you change it to pass the index by reference, the calls can cooperate:

void treeToArray(Node* n, int values[], int& index) {
     // start first call with index = 0
     if(n == NULL)
          return;
     if(n->left != NULL)
          treeToArray(n->left, values, index);
     // the left subtree call used a reference to the same
     // index variable, so any modification is visible here too

     values[index] = n->data;
     // we write our node data after the left subtree
     // (using the final value of index from the left subtree call)
     index++;
     // this affects the index in any parent call

     if(n->right != NULL)
          treeToArray(n->right, values, index);
     // the right subtree also advances the same index value
}

Note that you could instead return the new index, but this is a smaller change to your existing code.

For reference, it would be easy to unit-test this function in isolation with some small trees and check the expected output. This would expose the bug before you had introduced a second tree and all the other machinery.

It works! I am very thankful! I was trying for hours to get this fixed.

Collectives™ on Stack Overflow

Binary Tree to Array: Wrong values inserted into Array

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related