binary tree problem

ok so i have a binary tree(not a search one)

i declared it using an array like this


a[7]=0 1 2 3 4 5 6//lets say

1 2 3 4 5 6 7

node 0 is the root and has the key 1
and i constructed the array like this [2*i+1]=left node key and [2*i+2]=right node key

the question is

i need to make an algorithm,exactly an bfs , over an height...lets say if i have
1 2 3 4 5 6 7 array and i want to make the sum of nodes with height 2
it will return me 4 5 6 7


its not hard but my theacher want to implement recursive and i kinda suck at recursive implementation


this is the code i've tried to implement...

Code:

---


#include "iostream"
#define MAX 1000
#define sent 777
using namespace std;
int arb[MAX];
void calculation(int h,int lvl,int y);

int main()
{       
        int i=0,k=0,h,lvl=0,y=1;
        cout<<"give the root a value ";
        cin>>arb[0];
        cout<<"give root brother a value ";
        cin>>arb[2*i+1]>>arb[2*i+2];
        for(i=1;i<MAX;i++)
        {
                cout<<"give value to the brothers of "<<arb[i]<<" ";
                cin>>arb[2*i+1]>>arb[2*i+2];
                cout<<"you want to introduce another node  ?0 yes 1 no";
                cin>>k;
                if(k==1)
                        break;
        }
        k=2*i+2;
       

        for(i=0;i<=k;i++)
                cout<<arb[i]<<" ";
        cout<<"introduce the height for calculation ";
        cin>>h;

        for(int j=1;j<h;j++)
        {
                lvl=2*lvl+1;
                j++;
        }

        calculat(h,lvl,y);
        return 0;

}
void calculation(int h,int lvl,int y)
{
int k=2;
cout<<arb[2*lvl+1]<<arb[2*lvl+2];


if(y<k)
{       
        y++;
        lvl++;
        calculat(h,lvl,y);
}
else
        return;

       
}

---

The nodes that you are calling brothers are usually called children. In your array, node[1] is the left child of node[0], and node[2] is the right child of node[0].

Also, there's a problem with your arb[] array. The arraysize is MAX, but if the user keeps adding nodes until i == MAX, there will be 2*MAX+1 elements. There's also a problem with the way you calculate k after the first for loop. Consider what happens if the user quits during the loop when i == MAX-1, compared to what happens if the user tries to continue one more time.

You're not clear about what you want to output. You say the "sum of the nodes with height 2" but you wrote "4 5 6 7" which is a list of the keys, not a sum. If you want a list of keys, you need another array to contain that list.

Are you required to implement this tree with an array of ints? It can be done, but it might be easier to visualize if you create a struct node consisting of an int value and two node* pointers (initially NULL), one to point to the left child and the other to point to the right child.

But you can do it with int arrays. You should pass at least 4 parameters to the recursive function (this assumes that you will never call it with a level in the tree that is not completely full):
(!) a pointer to the position in the tree (array) that represents the root of the SUBTREE that the function will work with
(2) the level in the SUBTREE that is to be output (or summed)
(3) a pointer to the position in the output array that the function can write to (or, if you just want a sum, a pointer to the variable that will accumulate the sum)
(4) the step size, which tells the function how to find the position in the array that it should send to its children

There are 2 parts to the recursive function: the base case which in this case tells it what to do when level==0, and the recursive case which tells it what to do otherwise -- call itself twice, once for the left child and once for the right child, reducing the level by 1 and adjusting the array pointer(s) appropriately.

So the body of the function consist of just 5 lines:

Code:

---

if (level == 0)
    you write this one
}
else {
    you write this one
    you write this one
}

---