{"id":"0ef33761-059b-483e-9939-2a601806179c","name":"Replace With Sum Of Larger","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of rwsol function. \"rwsol\" function is expected to replace a node's value with sum of all nodes greater than it.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video for clarity. Use the statis sum data member to complete your code.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\nvoid display(Node* node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \" <- \" + to_string(node->data) + \" -> \";\n\n string left = (node->left == nullptr) ? \".\" : \"\" + to_string(node->left->data);\n string right = (node->right == nullptr) ? \".\" : \"\" + to_string(node->right->data);\n\n str = left + str + right;\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nvoid replacewithsum(Node* &root){\n// Write your code here\n \n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n,0);\n for(int i=0;i<n;i++){\n string x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n\n Node* root= construct(arr);\n \n replacewithsum(root);\n\n display(root);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n static int sum = 0;\r\n public static void rwsol(Node node){\r\n // write your code here\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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n rwsol(root);\r\n\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.data = key\n \nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n top.state+=1\n else:\n st.pop();\n return root; \n \ndef display(node) :\n if (node == None):\n return;\n \n s = \" <- \" + str(node.data) + \" -> \";\n left = \".\" if node.left is None else \"\"+str(node.left.data);\n right = \".\" if node.right is None else \"\" + str(node.right.data);\n \n s=left + s + right;\n print(s);\n \n display(node.left);\n display(node.right);\n \n\ndef replacewithsum(root):\n# Write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\n\nroot=construct(arr)\n\nreplacewithsum(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"311 <- 224 -> 87\r\n336 <- 311 -> 274\r\n. <- 336 -> .\r\n. <- 274 -> .\r\n162 <- 87 -> 0\r\n. <- 162 -> .\r\n. <- 0 -> .","questionVideo":"https://www.youtube.com/embed/0lMnG_9wcsU","hints":[],"associated":[{"id":"33d9abe5-90fe-4c12-9462-83f37a9340f3","name":"What is the space complexity of replace with largest sum?","slug":"what-is-the-space-complexity-of-replace-with-largest-sum","type":4},{"id":"7313c20d-212a-4d90-a89f-4b26cb20cb4d","name":"What is the time complexity of replace with largest sum?","slug":"what-is-the-time-complexity-of-replace-with-largest-sum","type":4},{"id":"ae959789-e7be-4e89-9755-170190622d1e","name":"Which data structure is used in replace with largest sum?","slug":"which-data-structure-is-used-in-replace-with-largest-sum","type":4},{"id":"f8c778bb-1071-4088-8b87-ede1b1ef6401","name":"What is the one extra property that makes a Binary Tree a BST?","slug":"what-is-the-one-extra-property-that-makes-a-binary-tree-a-bst","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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"3c22d1cb-1ef7-48db-b8ba-d780163dee1e","name":"Replace With Sum Of Larger","slug":"replace-with-sum-of-larger","type":1}],"next":{"id":"e531028a-ba4c-41a5-b204-50912c7e36b5","name":"Replace With Sum Of Larger","type":3,"slug":"replace-with-sum-of-larger"},"prev":{"id":"5879bce5-4ee0-4dec-903f-c729ac5b36be","name":"Remove Node from BST","type":3,"slug":"remove-node-from-bst"}}}

Replace With Sum Of Larger

1. You are given a partially written BST class. 2. You are required to complete the body of rwsol function. "rwsol" function is expected to replace a node's value with sum of all nodes greater than it. 3. Input and Output is managed for you. Note -> Please watch the question video for clarity. Use the statis sum data member to complete your code.

{"id":"0ef33761-059b-483e-9939-2a601806179c","name":"Replace With Sum Of Larger","description":"1. You are given a partially written BST class.\r\n2. You are required to complete the body of rwsol function. \"rwsol\" function is expected to replace a node's value with sum of all nodes greater than it.\r\n3. Input and Output is managed for you. \r\n\r\nNote -> Please watch the question video for clarity. Use the statis sum data member to complete your code.","inputFormat":"Input is managed for you","outputFormat":"Output is managed for you","constraints":"None","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nstruct Node{\n int data;\n Node* left;\n Node* right;\n Node(int val){\n data=val;\n left=nullptr;\n right=nullptr;\n }\n};\n\n\nNode* construct(vector<int> & arr){\n Node* root=new Node(arr[0]);\n pair<Node*,int> p={root,1};\n\n stack<pair<Node*,int>> st;\n st.push(p);\n\n int idx=1;\n while(!st.empty()){\n \n if(st.top().second==1){\n st.top().second++;\n if(arr[idx]!=-1){\n st.top().first->left=new Node(arr[idx]);\n pair<Node*,int> lp={st.top().first->left,1};\n st.push(lp);\n }\n else{\n st.top().first->left=nullptr;\n }\n idx++;\n }\n else if (st.top().second == 2) {\n st.top().second++;\n if (arr[idx] != -1) {\n st.top().first->right = new Node(arr[idx]);\n pair<Node*,int> rp={st.top().first->right,1};\n st.push(rp);\n } else {\n st.top().first->right = nullptr;\n }\n idx++;\n }\n else {\n st.pop();\n }\n\n }\n return root;\n}\nvoid display(Node* node) {\n if (node == nullptr) {\n return;\n }\n\n string str = \" <- \" + to_string(node->data) + \" -> \";\n\n string left = (node->left == nullptr) ? \".\" : \"\" + to_string(node->left->data);\n string right = (node->right == nullptr) ? \".\" : \"\" + to_string(node->right->data);\n\n str = left + str + right;\n cout << str << endl;\n\n display(node->left);\n display(node->right);\n}\n\nvoid replacewithsum(Node* &root){\n// Write your code here\n \n}\n\nint main(){\n int n;\n cin >> n;\n vector<int> arr(n,0);\n for(int i=0;i<n;i++){\n string x;\n cin >> x;\n if(x==\"n\"){\n arr[i]=-1;\n\n }\n else{\n arr[i]=stoi(x);\n }\n }\n\n Node* root= construct(arr);\n \n replacewithsum(root);\n\n display(root);\n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n public static class Node {\r\n int data;\r\n Node left;\r\n Node right;\r\n\r\n Node(int data, Node left, Node right) {\r\n this.data = data;\r\n this.left = left;\r\n this.right = right;\r\n }\r\n }\r\n\r\n public static class Pair {\r\n Node node;\r\n int state;\r\n\r\n Pair(Node node, int state) {\r\n this.node = node;\r\n this.state = state;\r\n }\r\n }\r\n\r\n public static Node construct(Integer[] arr) {\r\n Node root = new Node(arr[0], null, null);\r\n Pair rtp = new Pair(root, 1);\r\n\r\n Stack<Pair> st = new Stack<>();\r\n st.push(rtp);\r\n\r\n int idx = 0;\r\n while (st.size() > 0) {\r\n Pair top = st.peek();\r\n if (top.state == 1) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.left = new Node(arr[idx], null, null);\r\n Pair lp = new Pair(top.node.left, 1);\r\n st.push(lp);\r\n } else {\r\n top.node.left = null;\r\n }\r\n\r\n top.state++;\r\n } else if (top.state == 2) {\r\n idx++;\r\n if (arr[idx] != null) {\r\n top.node.right = new Node(arr[idx], null, null);\r\n Pair rp = new Pair(top.node.right, 1);\r\n st.push(rp);\r\n } else {\r\n top.node.right = null;\r\n }\r\n\r\n top.state++;\r\n } else {\r\n st.pop();\r\n }\r\n }\r\n\r\n return root;\r\n }\r\n\r\n public static void display(Node node) {\r\n if (node == null) {\r\n return;\r\n }\r\n\r\n String str = \"\";\r\n str += node.left == null ? \".\" : node.left.data + \"\";\r\n str += \" <- \" + node.data + \" -> \";\r\n str += node.right == null ? \".\" : node.right.data + \"\";\r\n System.out.println(str);\r\n\r\n display(node.left);\r\n display(node.right);\r\n }\r\n\r\n static int sum = 0;\r\n public static void rwsol(Node node){\r\n // write your code here\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 Integer[] arr = new Integer[n];\r\n String[] values = br.readLine().split(\" \");\r\n for (int i = 0; i < n; i++) {\r\n if (values[i].equals(\"n\") == false) {\r\n arr[i] = Integer.parseInt(values[i]);\r\n } else {\r\n arr[i] = null;\r\n }\r\n }\r\n\r\n Node root = construct(arr);\r\n rwsol(root);\r\n\r\n display(root);\r\n }\r\n\r\n}"},"python":{"code":"import sys\nimport math\n\nclass Node:\n def __init__(self, key,left,right):\n self.left = left\n self.right = right\n self.data = key\n \nclass Pair:\n def __init__(self,node,state):\n self.node = node\n self.state = state\n\ndef construct(arr):\n root=Node(arr[0],None,None)\n rtp=Pair(root,1);\n \n st=[]\n st.append(rtp);\n \n idx=0;\n while(len(st)>0):\n top=st[-1];\n if top.state==1:\n idx+=1\n if(arr[idx]!=None):\n top.node.left = Node(arr[idx], None, None);\n lp = Pair(top.node.left, 1);\n st.append(lp);\n else:\n top.node.left=None;\n top.state+=1\n elif top.state==2:\n idx+=1\n if(arr[idx]!=None):\n top.node.right = Node(arr[idx], None, None);\n rp = Pair(top.node.right, 1);\n st.append(rp);\n else:\n top.node.right=None;\n top.state+=1\n else:\n st.pop();\n return root; \n \ndef display(node) :\n if (node == None):\n return;\n \n s = \" <- \" + str(node.data) + \" -> \";\n left = \".\" if node.left is None else \"\"+str(node.left.data);\n right = \".\" if node.right is None else \"\" + str(node.right.data);\n \n s=left + s + right;\n print(s);\n \n display(node.left);\n display(node.right);\n \n\ndef replacewithsum(root):\n# Write your code here\n \n \nn=int(input())\nvalues = list(map(str, input().split()))\narr=[0]*n\nfor i in range(0,n):\n if values[i]!=\"n\":\n arr[i]=int(values[i])\n else:\n arr[i]=None\n\nroot=construct(arr)\n\nreplacewithsum(root)\ndisplay(root)"}},"points":10,"difficulty":"easy","sampleInput":"15\r\n50 25 12 n n 37 n n 75 62 n n 87 n n","sampleOutput":"311 <- 224 -> 87\r\n336 <- 311 -> 274\r\n. <- 336 -> .\r\n. <- 274 -> .\r\n162 <- 87 -> 0\r\n. <- 162 -> .\r\n. <- 0 -> .","questionVideo":"https://www.youtube.com/embed/0lMnG_9wcsU","hints":[],"associated":[{"id":"33d9abe5-90fe-4c12-9462-83f37a9340f3","name":"What is the space complexity of replace with largest sum?","slug":"what-is-the-space-complexity-of-replace-with-largest-sum","type":4},{"id":"7313c20d-212a-4d90-a89f-4b26cb20cb4d","name":"What is the time complexity of replace with largest sum?","slug":"what-is-the-time-complexity-of-replace-with-largest-sum","type":4},{"id":"ae959789-e7be-4e89-9755-170190622d1e","name":"Which data structure is used in replace with largest sum?","slug":"which-data-structure-is-used-in-replace-with-largest-sum","type":4},{"id":"f8c778bb-1071-4088-8b87-ede1b1ef6401","name":"What is the one extra property that makes a Binary Tree a BST?","slug":"what-is-the-one-extra-property-that-makes-a-binary-tree-a-bst","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":"af4e5bec-9225-4f5f-a99b-97b23e8cf431","name":"Binary Search Tree For Beginners","slug":"binary-search-tree-for-beginners","type":0},{"id":"3c22d1cb-1ef7-48db-b8ba-d780163dee1e","name":"Replace With Sum Of Larger","slug":"replace-with-sum-of-larger","type":1}],"next":{"id":"e531028a-ba4c-41a5-b204-50912c7e36b5","name":"Replace With Sum Of Larger","type":3,"slug":"replace-with-sum-of-larger"},"prev":{"id":"5879bce5-4ee0-4dec-903f-c729ac5b36be","name":"Remove Node from BST","type":3,"slug":"remove-node-from-bst"}}}
plane

Editor

Loading...

Replace With Sum Of Larger

easy

1. You are given a partially written BST class. 2. You are required to complete the body of rwsol function. "rwsol" function is expected to replace a node's value with sum of all nodes greater than it. 3. Input and Output is managed for you. Note -> Please watch the question video for clarity. Use the statis sum data member to complete your code.

Constraints

None

Format

Input

Input is managed for you

Output

Output is managed for you

Example

Sample Input

15 50 25 12 n n 37 n n 75 62 n n 87 n n

Sample Output

311

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode