Problem on finding the number of leave node in a binary tree in C++ using array

user_16250549 0
Viewed 66

I am working on a C++ code to find out the number of leave node in a binary tree using array input my code is:

int leaf(int data[],int size) {
    int result = 0;
    for (int i = 0; i <= size; i++) {
        if (data[i] == -1)
            i++;
        if (((data[(2*i)+1] == -1) && (data[(2 * i) +2] == -1)) || ((data[(2 * i) +1] == NULL) && (data[(2 * i) +2] == NULL)))
            result++;
    }
    return result;
}

int main(){
    int data[]= { 1,9, 6, 8 ,12, 2,-1 ,10, -1 ,-1 ,-1, 5 };
    int size = 12;
    cout << "count of leave node: " << leaf(data, size)<< endl;
}

In the array, the element -1 is the empty node. The tree is like:

       1
     /    \
    9      6
   / \    /
  8  12  2
 /      /
10     5

The total number of the leave node should be 3 which is (12,10,5), but the result of my code is 2. Can I know what wrong with my code and how to fix it. Big Thanks!

binary-tree arrays c++
1 Answers

Some issues:

  • When the for loop variable gets to equal size you will have an out of bounds index-access to data. The loop should exit in that case -- size is an invalid index, so use i < size as loop condition.

  • Your for loop increments the loop variable with i++; there should be no reason to increment i on top of that when you find a -1 value in the data. What if i will be out of bounds by doing that? What if the next data element also has a -1 value? In either case your code goes wrong. Instead use data[i] != -1 as a condition for the rest of the logic in the loop's body.

  • You should check that the index you use for data is not out of bounds, before actually making that index access. It is not safe to compare an out of bounds data entry with NULL: the value of an out of bounds access is undefined and int should never have to be compared with NULL. NULL is used in the context of pointers.

  • You should also foresee the case where the left child is -1 and the right child is out of bounds.

Here is a fix for those issues:

int leaf(int data[], int size) {
    int result = 0;
    for (int i = 0; i < size; i++) {
        if ( data[i] != -1 &&
                 (2*i+1 >= size || data[2*i+1] == -1) &&
                 (2*i+2 >= size || data[2*i+2] == -1) )
            result++;
    }
    return result;
}

This logic assumes that the array will be organised like a complete tree. Some array encodings like this will not have two -1 entries for filling up the "children" of another -1 entry, but just omit them, making the formula 2*i+1 and 2*i+2 invalid.

Take for example this tree:

       1
        \
         2
          \
           3

If the encoding is a complete tree encoding, then it will be {1, -1, 2, -1, -1, -1, 3}. If it is the more compact encoding where -1 entries will not have children entries, then it will be {1, -1, 2, -1, 3}.

Your example does not show which of the two encodings you are dealing with as it would turn out to be the same array for your example tree. If it is the later encoding, you need a different algorithm altogether.

user_54598390
Related