- Practice
- Algorithms
- Search
- Cut the Tree
- Discussions

# Cut the Tree

# Cut the Tree

gkeller2 + 7 comments I just finished solving this problem and have a couple of comments/suggestions. First, I agree with several of the comments expressed so far: it's not clear in the problem description that an undirected graph is provided as input instead of a tree, and one has to make the working assumption that the first node provided is the root of the tree to work with. It would be great if these two points could be clarified for future enthusiasts/hackers that try to solve the problem.

Second (and this issue may have to do more with HackerRank's platform than with this problem in particular), my solution (written in Python) was failing for test cases 6 and above due to the size of the input graph. However, the only message I was getting about it was "Runtime error", which is rather cryptic in this case. Hadn't I downloaded one of the bigger test cases and run it in my computer, I wouldn't have figured out that the problem was that I was running out of memory and that I needed to devise an iterative solution instead of a recursive one.

I hope these comments/suggestions are taken in good faith; my only intention is to help improve the quality of the site.

Cheers, Gaston

Shafaet + 2 comments Thanks for your suggestions. What was the error that you got in your PC? Recursive solutions can give Runtime error when it reaches the stack size limit. Do other judges give different errors in this case?

gkeller2 + 0 comments The precise error message return by the Python interpreter is "RuntimeError: maximum recursion depth exceeded". RuntimeError is a rather general exception, only being raised when a more fitting error category couldn't be found. Therefore, showing the full error message would be more enlightening.

yugesh + 1 comment First i was using recursive method and i was facing the same problem of run time error then after reading your comment i changed it to iterative method but still i am getting "terminated due to timeout" . Can you please help

def dfs(v,visited,tree,v1,lis):

`visited[v]=True total=tree[v] newlis=[] for x in lis[v]: if x!=v1: newlis.append(x) total=total+tree[x] while newlis: y=newlis.pop() visited[y]=True for z in lis[y]: if visited[z]==False and z!=v1: visited[z]=True newlis.append(z) total=total+tree[z] return total`

xcabel + 0 comments If I understand this correctly, are you recording the list of all ancestors for current node? you don't need that but only need to record the farther. Otherwise it is not memory efficient.

Sid_S + 0 comments "one has to make the working assumption that the first node provided is the root"

I disagree. You just lucked out because all the test cases allowed you to make that assumption.

If you think it through, you'll see that any leaf node will do for a root, and the first node provided does not have to be a leaf.

tas123 + 0 comments Thanks for ur suggestions. helped a lot

denizsayin + 1 comment About your comment's recursion part, I did it using a recursive solution in C++, therefore if you have no memory leaks or accidental copying, I think simply increasing the recursion limit in Python using "sys.setrecursionlimit(x)" would be fine.

rochakgupta + 0 comments Thanks for this comment. I always use C++ and had implemented the recursive way. The problem was the number of parameters being passed to the recursive function. Having decreased that to 1, I got AC perfectly.

vivekGhosh + 0 comments Hi gkeller2, I wrote the following code, treating the tree as a graph and employing dfs. However, I am getting errors from testcase6 onwards, and i don't know if it's a stack memory issue or not, because I checked testcase5, and it is just as big as testcase6, can you help me decipher what's wrong with my code?

import java.util.*; class treeCut { private int values[]; private int tree[][]; private int visited[]; private int n; private int sum; private int min; public treeCut(int n) { this.n = n; values = new int[n+1]; tree = new int[n+1][n+1]; visited = new int[n+1]; sum = 0; min = Integer.MAX_VALUE; } public void addValue(int node, int value) { values[node] = value; sum+=value; } public void newEdge(int u, int v) { setEdge(u,v); setEdge(v,u); } private void setEdge(int u, int v) { tree[u][0]+=1; tree[u][tree[u][0]] = v; } private int traverse(int node) { visited[node] = 1; int treeSum = values[node]; int i,diff = 0; // System.out.println("\n"+"At node "+node); for(i = 1;i<=tree[node][0];i++) { if(visited[tree[node][i]]==0) treeSum+=traverse(tree[node][i]); } // System.out.println("For node - "+node); // System.out.println("Sum from this tree - "+treeSum); // System.out.println("Rest of the tree - "+(sum-treeSum)); diff = (int)Math.abs((2*treeSum)-sum); // System.out.println("Difference - "+diff); if(diff<min) min = diff; return treeSum; } public int getMinSum() { // System.out.println("Net Tree Sum - "+sum); traverse(1); return min; } public static void main(String args[]) { try { Scanner s = new Scanner(System.in); int n = s.nextInt(); int i,u,v; treeCut temp = new treeCut(n); for(i = 1;i<=n;i++) temp.addValue(i,s.nextInt()); for(i = 1;i<n;i++) { u = s.nextInt(); v = s.nextInt(); temp.newEdge(u,v); } System.out.println(temp.getMinSum()); } catch(Exception e) { System.out.println("Exception caught - "+e); } } }

shashank_cs2 + 1 comment Another assumption -> That there are no cycles in the graph

vlomako + 1 comment The graph is a tree. Trees haven't cycles. And any node can serve as a root.

Sid_S + 0 comments any node can serve as a root

That is only true if there is no limit to how many children a node can have.

For instance, if you look at the simple tree shown at the top of the challenge, you can only use node 3 as a root if nodes are allowed to have three children.

visheshy + 2 comments The input represents a tree. Usually one would expect a consistent parent child connection pairs, however in example tests (4, 5) breaks this. Would have been better if it was (5, 4).

Ocelotl + 0 comments Yes, please. This kind of input is a problem by itself and it is an unnecessary obstacle for the actual problem at hand.

Mandrenkov + 0 comments Switching the parent-child relationship is actually a pretty standard thing to do in programming contests. Although this does not necessarily test your ability to write an algorithm that solves the given problem, it

*does*make you pay attention to your assumptions.Generally speaking, being conscious of your assumptions is part of being a good programmer.

nboddula + 8 comments Thanks a lot. Really a nice problem to solve. Had to think for few hours and was going back n forth trying to reduce complexity, debugging for cases where I dint mentally account for.

This problem can be solved in O( V + E ) complexity with two traversals of DFS.

For those who are stuck, here are hints: 1. Dont think of it as a Tree problem. Approach it as a GRAPH. 2. Use first run of DFS to compute a value (not telling what it is :p) that you think will help you solve the problem. 3. The real breakthrough happens during the second run of DFS. You have to look at your values from first run of DFS and identify what condition always holds true. If you figure that out, the logic is simple (five lines of code for DFS again) and you are done.

Hopefully, this helps. Happy coding.

raam_arvind93 + 0 comments Wah! what a subtle hint for the solution :P

Scortius + 0 comments Just a note on your complexity calculation: a tree will always have V-1 edges, thus O(V).

nevertoolate + 0 comments That's essentially my solution. In recursive form it's quite compact: two calls to DFS. But then you need to turn it into an iterative algorithm or you'll run out of recursion space. You still need to keep a stack of traces though or you'll lose information.

kashyap2108 + 1 comment Well did u implemented DfS using recursion or stack?

nevertoolate + 0 comments I used a stack of lists in a iteartive algorithm. No recursion.

hockeyshark315 + 0 comments Great hints! It is actually possible to do this only traversing the graph once (one DFS). Hint: try at the beginning, calculating half of the total weight of the tree. Keep a running minimum as you traverse the tree....

10ne_coder + 0 comments I did it in only one DFS traversal but used hashmap all because of your hint !!! Thanks a lot.

cavehubiao + 0 comments thanks for advice , one time dfs

# Enter your code here. Read input from STDIN. Print output to STDOUT import sys import copy n = int(raw_input()) point = [int(x) for x in raw_input().split(' ')] sp = sum(point) v = set([]) mi = float('inf') def dfs(p): global mi v.add(p) r = point[p - 1] for k in table[p]: if k in v: continue s = dfs(k) mi = min(mi, abs(sp - s - s)) r += s return r def nr_dfs(p): global mi sta = [p] while len(sta) > 0: t = sta[-1] if len(donetable[t]) == 0: r = point[t - 1] for k in table[t]: #print k, t if t not in pre or k != pre[t]: r += valuetable[k] mi = min(mi, abs(sp - r - r)) valuetable[t] = r sta.pop() for k in donetable[t]: pre[k] = t sta.append(k) donetable[k].remove(t) donetable[t] = set([]) table = {} for i in range(n - 1): [p, q] = [int(x) for x in raw_input().split(' ')] if p in table: table[p].add(q) else: table[p] = set([q]) if q in table: table[q].add(p) else: table[q] = set([p]) donetable = copy.deepcopy(table) valuetable = {} pre = {} nr_dfs(1) print mi

k_sai_kumar + 0 comments You only need one dfs call

scp_manitrix + 3 comments Can anyone tell me if the tree in the question is a binary tree or a mango tree(meaning having multiple child nodes) ?? ;).. also tree seems to be creating an illusion with respect to graph approach needed to solve the problem

PRASHANTB1984 + 1 comment do read the editorial for a working approach!

avinashshenoy97 + 1 comment So is it a binary tree or a mango tree?

TboneMcScreedle + 0 comments banana tree

cdv20 + 0 comments that info is irrelevant. it's best to assume it as a acyclic graph and proceed.

mgperson + 1 comment Agree with cdv20. The implementation is the same for a binary or n-ary tree (undirected acyclic graph). You look at all the connections for each vertex that haven't been visited.

itsmedurgesh + 1 comment binary or n-ary tree will make difference in storgae as I can store binary tree as array and work more efficiently from there. So yes implementation can differ.

slashvar1 + 0 comments Nop, because it's really a graph, and thus each node (in case it was a binary tree) may have 3 "children" since there's no direction in the relation between nodes.

You must understand tree in graph sens: an undirected acyclic connected graph (no cycle, a single connected component and exactly order-1 edges).

The only relevant information you can get from the fact that we got a tree is that there's no cycle. This has two consequences: cutting one edge break connectivity and in a DFS traversal you don't need to mark vertices, just remember the parent of the current vertex.

cx473 + 2 comments Tip for Java users: if you're getting timeouts, it could be because Java I/O with scanner (like in the starter code provided) is too slow. Try using a faster custom-made input reader.

Was getting timeouts for all test cases from #6. Changed input scanner to this FastReader class provided by geeksforgeeks, and the same implementation passed all test cases without a sweat.

raghavg06 + 0 comments thanks that helped me also

dasilva_carlose1 + 0 comments OMG, this comment was so useful. I was starting to rethink my career as I couldn't find out why my code was timming out, turn out that was the scanner. Thank you ^^

jmichela + 4 comments The empty starter code for the Java implementations does not even complete cases 6-19 in time. All timeouts. Save yourself a few hours of headache and switch from Scanner to a BufferedReader. My original implementation of reccursive DFS completed just fine after I did this.

Change the given main method to this code below:

public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH"))); int n = Integer.parseInt(in.readLine()); int[] data = new int[n]; String[] dataItems = in.readLine().split(" "); for (int i = 0; i < n; i++) { int dataItem = Integer.parseInt(dataItems[i]); data[i] = dataItem; } int[][] edges = new int[n-1][2]; for (int i = 0; i < n-1; i++) { String[] edgesRowItems = in.readLine().split(" "); for (int j = 0; j < 2; j++) { int edgesItem = Integer.parseInt(edgesRowItems[j]); edges[i][j] = edgesItem; } } int result = cutTheTree(data, edges); bufferedWriter.write(String.valueOf(result)); bufferedWriter.newLine(); bufferedWriter.close(); }

ara_mambreyan + 0 comments Thank you so much! You are my hero!

fabriziocucci + 0 comments It works like a charm!

thirumal_bhukya + 1 comment It's not working though i changed main method and i used bfs for traversal..

jmichela + 0 comments Try DFS instead of BFS. You may also want to try and put in some optimizations so that you do not need to recacluate the sum of subtrees if you have already done so.

Let me know how that works for you.

calebmbakwe + 0 comments My solution is still timing out after changing the main method. Am I geting something wrong? See my code here:

class Result { static HashSet<Integer> set; static int[][] edges; static Stack<Node> stack; static int[] data; /* * Complete the 'cutTheTree' function below. * * The function is expected to return an INTEGER. * The function accepts following parameters: * 1. INTEGER_ARRAY data * 2. 2D_INTEGER_ARRAY edges */ public static int cutTheTree(int[] data, int[][] edges) { // Write your code here Result.edges = edges; Result.set = new HashSet<>(); Result.stack = new Stack<>(); Result.data = data; int max = 0; for(int i: data){ max += i; } Node start = new Node(data[0], 1); set.add(1); stack.push(start); Node v, temp; int min = max; // System.out.println(data + " " + edges + " " + max); while(!stack.isEmpty()){ v = getUnvisited(stack.peek()); // System.out.println(v); if(v == null){ temp = stack.pop(); min = Math.min(min, Math.abs((max - (temp.children + temp.data)) - (temp.children + temp.data))); if(!stack.isEmpty()){ stack.peek().children += (temp.children + temp.data); } } else{ set.add(v.index); stack.push(v); } } return min; } static Node getUnvisited(Node v){ for(int i = 0; i < Result.edges.length; i++){ if((Result.edges[i][0] == v.index) && (!Result.set.contains(Result.edges[i][1]))){ return new Node(Result.data[Result.edges[i][1] - 1], Result.edges[i][1]); } else if((Result.edges[i][1] == v.index) && (!Result.set.contains(Result.edges[i][0]))){ return new Node(Result.data[Result.edges[i][0] - 1], Result.edges[i][0]); } } return null; } static class Node{ int data, index, children; public Node(int d, int i){ this.data = d; this.index = i; this.children = 0; } public String toString(){ return "{" + index + " - " + data + " - " + children + "}"; } } }

auuuree_yrrrr + 1 comment simple use dfs

#include<bits/stdc++.h> using namespace std; vector<int> *tree; vector<int> treedata; vector<bool> vis; int n,u,v,total,ans; int dfs(int u) { int below = treedata[u]; vis[u]=true; for(int i=0;i<tree[u].size();i++) { if(vis[tree[u][i]]==false) below += dfs(tree[u][i]); } if(abs(total - (2*below)) < ans) { ans = abs(total - (2*below)); } return below; } int main() { cin>>n; tree = new vector<int>[n+1]; treedata.resize(n+1); vis.resize(n+1,false); total = 0; ans = 1e9; for(int i=1;i<n+1;i++) { cin>>treedata[i]; total += treedata[i]; } for(int i=1;i<n;i++) { cin>>u>>v; tree[u].push_back(v); tree[v].push_back(u); } dfs(1); cout<<ans<<endl; return 0; }

sun_moon_star515 + 1 comment [deleted]auuuree_yrrrr + 1 comment Suppose u have a tree of total value sum as 1000 Then u separated a node of value say 200 Then new trees will be of size 800 and 200 800-200=600 which can be written as 1000-2*(200)=60

auuuree_yrrrr + 2 comments and why u copied my solution did u tried on your own

sun_moon_star515 + 0 comments I was not trying to copy your solution. i jsut wanted to verify it. Thank you for the explanation.

sun_moon_star515 + 0 comments I will remove yours and try my own. Thank you!

byungkune_choi + 1 comment Can any one tell me how the tree is constructed based on the input? It's not clear to me how to construct that tree

Herkar + 1 comment Since a tree is a graph, it can be represented as a set of nodes and edges, of which we are given the edges in the form of pairs of nodes. A tree does not have to be represented as a parent-child relationship, as that is completely dependent on which node it's rooted in, which is not given in the problem statement or input data.

hawkik + 1 comment WRONG! The problem statement clearly indicates that first node is the root of the Tree.

Quoting from problem statment: "The next line will contain NN integers separated by a single space, i.e. the values assigned to each of the vertices (where the first one is the root of the tree)."

See the last part there -> "(where the first one is the root of the tree)"

So the first node is supposed to be the root of the tree. But the test case data does not seem to honor this.

Which completely invalidates this test.

I see this all the time in Hacker Rank where the problem description is misleading or erroneous which completely SUCKS!!!

HackerRank MUST VALIDATE THAT ALL CONDITIONS ON ALL TESTS ARE AS STATED IN THE PROBLEM AND MUST MAKE SURE THE SAMPLE DATA IS INDICATIVE OF ALL THE DATA IN THE TEST CASES.

Scortius + 2 comments 1) This problem has no dependence on which node you choose to be the root. The answer will always be the same assuming there are no edges that result in ties.

2) The edges are undirected, which means you should assume they are bidirectional. Thus the ordering of the vertex pairs should not affect your implementation.

xcabel + 0 comments Yes. I totally agree with you on these two points. In such same reason, there is no need for stating that the left node of the first edge as the root in the description. This kind of narrative easily leads to misunderstanding that the edges provided in a tree convention parent-->child

asdjadsa + 0 comments Agreed, with the sole proviso that the node you choose under the assumption of the problem statement is actually a root.

"The answer will always be the same assuming there are no edges that result in ties." There is no need for that assumption.

vladbel + 0 comments Isn't it in the sample input the line 6 shall be "5 4", not "4 5"?

ronitrex + 0 comments Brilliant problem!

I passed all the test cases except Test cases numbered 7, 8, 15, 16, 17 which are giving a 'Segmentation Fault' error. But after manually testing the aforementioned testcases on my system, I am able to get the desired results.

Can't really figure out a way out of these segmentation errors.

Sort 99 Discussions, By:

Please Login in order to post a comment