{"id":"cbb4288a-b44d-4bd8-accc-6b8d34492ece","name":"Node With Maximum Subtree Sum","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find and print the node which has the subtree with largest sum. Also print the sum of the concerned subtree separated from node's value by an '@'. Refer the question video for clarity.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"<data of node with subtree having largest sum>@<the largest sum of a subtree>","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<iostream>\nusing namespace std;\nint c= INT_MAX;\nint flloor= INT_MIN;\n\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key){\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n ){\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\n \n if(st.size()>0){\n st.top()->children.push_back(t);\n }else{\n root=t;\n }\n st.push(t);\n }\n }\n return root;\n}\n\nint msum =0;\nint msumnode =0;\n\nint subsumtree(Node *node)\n{\n //Write your code here\n}\n\n\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n int k;\n cin>>k;\n Node *root=construct(arr,n);\n subsumtree(root);\n cout<<msumnode<<\"@\"<<msum<<endl;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\n\n\nclass Node:\n \n def __init__(self, data):\n self.data = data\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(data): \n temp = Node(data)\n return temp\n \ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n\n\ndef nodewithmaxsum(node):\n # Write your code here\n\n \nlst = []\n# number of elements as input\nn = int(input())\n\nlst = list(map(int, input().split()))\n \n\nroot = constructor(lst,n) \nmsum = -math.inf\nmsumnode = 0\nnodewithmaxsum(root)\nprint(str(msumnode) + \"@\" + str(msum))"}},"points":10,"difficulty":"medium","sampleInput":"20\r\n10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1","sampleOutput":"30@130","questionVideo":"https://www.youtube.com/embed/TKqOZ3tp1D8","hints":[],"associated":[{"id":"54f27cdf-50f4-4eb0-bbd2-410dd463839b","name":"when we have to update the value of mSum?","slug":"when-we-have-to-update-the-value-of-msum","type":4},{"id":"cc11626d-9483-4268-b815-222a784ddeb8","name":"What will be the time complexity of \"Node with Maximum Subtree sum\"?","slug":"what-will-be-the-time-complexity-of-node-with-maximum-subtree-sum","type":4},{"id":"d969941d-3ebd-4f06-b21e-7062d9e3b5b0","name":"What will be the auxiliary space complexity of \"Node with Maximum Subtree sum\"?","slug":"what-will-be-the-auxiliary-space-complexity-of-node-with-maximum-subtree-sum","type":4},{"id":"fe697f7e-73f9-4c67-8059-5b732d31d95a","name":"what will be the initial value of mSum ans mSumNode","slug":"what-will-be-the-initial-value-of-msum-ans-msumnode","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"98a883c9-ff2a-44d4-9426-4dae66a23aba","name":"Node With Maximum Subtree Sum","slug":"node-with-maximum-subtree-sum","type":1}],"next":{"id":"90e258dc-5c9d-4698-893f-5d9d6521d896","name":"Node with Maximum Subtree Sum:","type":3,"slug":"node-with-maximum-subtree-sum"},"prev":{"id":"592f81a7-be47-44d9-8b1a-170dbe6a19fc","name":"Kth Largest Element In Tree","type":3,"slug":"kth-largest-element-in-tree"}}}

Node With Maximum Subtree Sum

1. You are given a partially written GenericTree class. 2. You are required to find and print the node which has the subtree with largest sum. Also print the sum of the concerned subtree separated from node's value by an '@'. Refer the question video for clarity. 3. Input is managed for you.

{"id":"cbb4288a-b44d-4bd8-accc-6b8d34492ece","name":"Node With Maximum Subtree Sum","description":"1. You are given a partially written GenericTree class.\r\n2. You are required to find and print the node which has the subtree with largest sum. Also print the sum of the concerned subtree separated from node's value by an '@'. Refer the question video for clarity.\r\n3. Input is managed for you.","inputFormat":"Input is managed for you","outputFormat":"<data of node with subtree having largest sum>@<the largest sum of a subtree>","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\n#include<iostream>\nusing namespace std;\nint c= INT_MAX;\nint flloor= INT_MIN;\n\nstruct Node{\n int data;\n vector<Node*>children;\n};\n\nNode *newNode(int key){\n\tNode *temp=new Node;\n\ttemp->data=key;\n\treturn temp;\n\n}\n\nNode *construct(int arr[],int n ){\n Node *root=NULL;\n stack<Node*>st;\n for(int i=0;i<n;i++){\n if(arr[i]==-1){\n st.pop();\n }else{\n Node *t=newNode(arr[i]);\n \n if(st.size()>0){\n st.top()->children.push_back(t);\n }else{\n root=t;\n }\n st.push(t);\n }\n }\n return root;\n}\n\nint msum =0;\nint msumnode =0;\n\nint subsumtree(Node *node)\n{\n //Write your code here\n}\n\n\n\nint main(){\n \n int n;\n cin>>n;\n \n int arr[n];\n for(int i=0;i<n;i++){\n cin>>arr[i];\n }\n int k;\n cin>>k;\n Node *root=construct(arr,n);\n subsumtree(root);\n cout<<msumnode<<\"@\"<<msum<<endl;\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n private static class Node {\r\n int data;\r\n ArrayList<Node> children = new ArrayList<>();\r\n }\r\n\r\n public static void display(Node node) {\r\n String str = node.data + \" -> \";\r\n for (Node child : node.children) {\r\n str += child.data + \", \";\r\n }\r\n str += \".\";\r\n System.out.println(str);\r\n\r\n for (Node child : node.children) {\r\n display(child);\r\n }\r\n }\r\n\r\n public static Node construct(int[] arr) {\r\n Node root = null;\r\n\r\n Stack<Node> st = new Stack<>();\r\n for (int i = 0; i < arr.length; i++) {\r\n if (arr[i] == -1) {\r\n st.pop();\r\n } else {\r\n Node t = new Node();\r\n t.data = arr[i];\r\n\r\n if (st.size() > 0) {\r\n st.peek().children.add(t);\r\n } else {\r\n root = t;\r\n }\r\n\r\n st.push(t);\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[] arr = new int[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n }\r\n\r\n Node root = construct(arr);\r\n // write your code here\r\n }\r\n\r\n}"},"python":{"code":"import math\n\n\nclass Node:\n \n def __init__(self, data):\n self.data = data\n self.child = []\n \n # Utility function to create a new tree node\ndef newNode(data): \n temp = Node(data)\n return temp\n \ndef constructor(lst,n):\n root = None\n stack = []\n for i in range(0,n):\n if lst[i]==-1:\n stack.pop()\n else:\n t= Node(lst[i])\n if len(stack) > 0:\n stack[-1].child.append(t)\n \n else:\n root=t\n \n stack.append(t)\n return root\n\n\ndef nodewithmaxsum(node):\n # Write your code here\n\n \nlst = []\n# number of elements as input\nn = int(input())\n\nlst = list(map(int, input().split()))\n \n\nroot = constructor(lst,n) \nmsum = -math.inf\nmsumnode = 0\nnodewithmaxsum(root)\nprint(str(msumnode) + \"@\" + str(msum))"}},"points":10,"difficulty":"medium","sampleInput":"20\r\n10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1","sampleOutput":"30@130","questionVideo":"https://www.youtube.com/embed/TKqOZ3tp1D8","hints":[],"associated":[{"id":"54f27cdf-50f4-4eb0-bbd2-410dd463839b","name":"when we have to update the value of mSum?","slug":"when-we-have-to-update-the-value-of-msum","type":4},{"id":"cc11626d-9483-4268-b815-222a784ddeb8","name":"What will be the time complexity of \"Node with Maximum Subtree sum\"?","slug":"what-will-be-the-time-complexity-of-node-with-maximum-subtree-sum","type":4},{"id":"d969941d-3ebd-4f06-b21e-7062d9e3b5b0","name":"What will be the auxiliary space complexity of \"Node with Maximum Subtree sum\"?","slug":"what-will-be-the-auxiliary-space-complexity-of-node-with-maximum-subtree-sum","type":4},{"id":"fe697f7e-73f9-4c67-8059-5b732d31d95a","name":"what will be the initial value of mSum ans mSumNode","slug":"what-will-be-the-initial-value-of-msum-ans-msumnode","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"b6a55c74-7dc3-45b6-a948-9dcbaebf9367","name":"Generic Tree For Beginners","slug":"generic-tree-for-beginners","type":0},{"id":"98a883c9-ff2a-44d4-9426-4dae66a23aba","name":"Node With Maximum Subtree Sum","slug":"node-with-maximum-subtree-sum","type":1}],"next":{"id":"90e258dc-5c9d-4698-893f-5d9d6521d896","name":"Node with Maximum Subtree Sum:","type":3,"slug":"node-with-maximum-subtree-sum"},"prev":{"id":"592f81a7-be47-44d9-8b1a-170dbe6a19fc","name":"Kth Largest Element In Tree","type":3,"slug":"kth-largest-element-in-tree"}}}
plane

Editor

Loading...

Node With Maximum Subtree Sum

medium

1. You are given a partially written GenericTree class. 2. You are required to find and print the node which has the subtree with largest sum. Also print the sum of the concerned subtree separated from node's value by an '@'. Refer the question video for clarity. 3. Input is managed for you.

Constraints

None

Format

Input

Input is managed for you

Output

@

Example

Sample Input

20 10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1

Sample Output

30@130

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode