CODEWITHSUNDEEP
c++recursiontree
Sam
Sam

Reputation: 43

find and return the sum of all nodes present in a generic tree in c++

I want to find sum of all nodes in tree (not binary) recursively, I have tried it but i am not getting right answer. Generally i struggle understanding how recursion work in a question and i am not able to understand it's working in. Please help

int sum(TreeNode<int>* root){

      int s = 0;
      for(int i=0; i<root->child.size(); i++){
            s += root->data;
            sum(root->child[i]);
      }
      return s;

}

Please take a look at the tree structure: Tree Structure Image

Upvotes: 0

Views: 2814

Answers (1)

nigel
nigel

Reputation: 158

For a generic tree with n children, you can think of the recurrence relation as:

sum(tree) = value(root) + sum(child[0]) + sum(child[1]) + ... + sum(child[n-1])

Then, the recursive solution is simply:

int sum(TreeNode<int>* root)
{
    // value(root)
    int s = root->data;

    // no. children
    int n = root->child.size();

    // + sum(child[0]) + sum(child[1]) + ... + sum(child[n-1])
    for (int i = 0; i < n; ++i) {
        s += sum(root->child[i]);
    }

    return s;
}

Upvotes: 4

Related Questions