« Sum of Nodes in a tree

Find sum of nodes

Given a generic tree, find and return the sum of all nodes present in the given tree.

Input format :

The first line of input contains data of the nodes of the tree in level order form. The order is: data for root node, number of children to root node, data of each of child nodes and so on and so forth for each node. The data of the nodes of the tree is separated by space.

Output Format :

The first and only line of output prints the sum of all nodes of the given generic tree.

Constraints:

Time Limit: 1 sec

Sample Input 1:

10 3 20 30 40 2 40 50 0 0 0 0 Sample Output 1:

190

Copy
1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6template <typename T>
7class TreeNode {
8   public:
9    T data;
10    vector<TreeNode<T>*> children;
11
12    TreeNode(T data) { this->data = data; }
13
14    ~TreeNode() {
15        for (int i = 0; i < children.size(); i++) {
16            delete children[i];
17        }
18    }
19};
20
21int sumOfNodes(TreeNode<int>* root) {
22    int ans = root->data;
23    for(int i=0; i<root->children.size(); i++){
24        ans += sumOfNodes(root->children[i]);
25    }
26    return ans;
27}
28
29TreeNode<int>* takeInputLevelWise() {
30    int rootData;
31    cin >> rootData;
32    TreeNode<int>* root = new TreeNode<int>(rootData);
33
34    queue<TreeNode<int>*> pendingNodes;
35
36    pendingNodes.push(root);
37    while (pendingNodes.size() != 0) {
38        TreeNode<int>* front = pendingNodes.front();
39        pendingNodes.pop();
40        int numChild;
41        cin >> numChild;
42        for (int i = 0; i < numChild; i++) {
43            int childData;
44            cin >> childData;
45            TreeNode<int>* child = new TreeNode<int>(childData);
46            front->children.push_back(child);
47            pendingNodes.push(child);
48        }
49    }
50
51    return root;
52}
53
54int main() {
55    TreeNode<int>* root = takeInputLevelWise();
56    cout << sumOfNodes(root);
57}