« Node with maximum child sum recursively

Node with maximum child sum

Given a generic tree, find and return the node for which sum of its data and data of all its child nodes is maximum. In the sum, data of the node and data of its immediate child nodes has to be taken.

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 contains the data of the node with maximum sum, as described in the task.

Constraints:

Time Limit: 1 sec

Sample Input 1 :

5 3 1 2 3 1 15 2 4 5 1 6 0 0 0 0

Sample Output 1 :

1

Copy
1#include <iostream>
2#include <queue>
3#include <vector>
4#include<climits>
5using namespace std;
6
7template <typename T>
8class TreeNode {
9   public:
10    T data;
11    vector<TreeNode<T>*> children;
12
13    TreeNode(T data) { this->data = data; }
14
15    ~TreeNode() {
16        for (int i = 0; i < children.size(); i++) {
17            delete children[i];
18        }
19    }
20};
21
22template <typename T>
23class MaxNodePair{
24    public:
25    TreeNode<T> *node;
26    int sum;
27};
28
29MaxNodePair<int>* maxSumNodeUtil(TreeNode<int>* root) {
30    // Write your code here
31    if(root == NULL){
32       MaxNodePair<int> *ans = new MaxNodePair<int>();
33       ans->node = NULL;
34       ans->sum = INT_MIN;
35       return ans;
36    }
37
38    int sum = root->data;
39    for(int i=0; i<root->children.size(); i++){
40        sum = sum + root->children[i]->data;
41    }
42
43    MaxNodePair<int> *ans = new MaxNodePair<int>();
44    ans->node = root;
45    ans->sum = sum;
46
47    for(int i=0; i<root->children.size(); i++){
48       MaxNodePair<int> *curr =  maxSumNodeUtil(root->children[i]);
49       if(ans->sum < curr->sum){
50           ans = curr;
51       }
52    }
53
54    return ans;
55}
56
57TreeNode<int>* maxSumNode(TreeNode<int>* root) {
58    return maxSumNodeUtil(root)->node;
59}
60
61TreeNode<int>* takeInputLevelWise() {
62    int rootData;
63    cin >> rootData;
64    TreeNode<int>* root = new TreeNode<int>(rootData);
65
66    queue<TreeNode<int>*> pendingNodes;
67
68    pendingNodes.push(root);
69    while (pendingNodes.size() != 0) {
70        TreeNode<int>* front = pendingNodes.front();
71        pendingNodes.pop();
72        int numChild;
73        cin >> numChild;
74        for (int i = 0; i < numChild; i++) {
75            int childData;
76            cin >> childData;
77            TreeNode<int>* child = new TreeNode<int>(childData);
78            front->children.push_back(child);
79            pendingNodes.push(child);
80        }
81    }
82
83    return root;
84}
85
86int main() {
87    TreeNode<int>* root = takeInputLevelWise();
88
89    TreeNode<int>* ans = maxSumNode(root);
90
91    if (ans != NULL) {
92        cout << ans->data;
93    }
94}