CODEWITHSUNDEEP
c++algorithmtreetree-traversal
Panda
Panda

Reputation: 527

How to get sum of nodes of a tree which has children in a list?

So I have a Tree which is like this:

class Tree{
public:
int data1;
string data2;
Animal animal;
std::list<Tree> children;
};

I am trying to calculate sum of data1 nodes at odd level, but I am not able to do so. I calculated sum of all nodes like this:

int addData1(const Tree* t, int sum){
    if(t == nullptr) {
        return sum;
    }
    else{
        int temp = 0;
        std::list<Tree> forest = t->children;
        std::list<Tree>::iterator it;

        for(it = forest.begin(); it != forest.end(); ++it){
            Tree curr = *it;
            temp += addData1(&curr, sum);
        }

        return t->data1 + temp;
    }
}

But I am unable to do so for odd levels, I tried it like this, but I get incorrect sum:

int addData1Odd(const Tree* t, bool odd, int sum){
    if(t == nullptr){
        return sum;
    }
    else{
        int temp = 0;
        std::list<Tree> forest = t->children;
        std::list<Tree>::iterator it;

        for(it = forest.begin(); it != forest.end(); ++it){
            Tree curr = *it;
            if(odd)
                temp += addData1Odd(&curr, !odd, sum);
        }

        return t->data1 + temp;
    }
}

I would appreciate any help.

Upvotes: 0

Views: 125

Answers (1)

Mattias De Charleroy
Mattias De Charleroy

Reputation: 338

You stop recursing if you are not on an odd level. You should still recurse, but not add it to your sum

Edit: Try this:

    for(it = forest.begin(); it != forest.end(); ++it){
        Tree curr = *it;
        temp += addData1Odd(&curr, !odd, sum);
    }

    if (odd)
       return t->data1 + temp;
    else
       return temp;

Upvotes: 3

Related Questions