We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cut the Tree
You are viewing a single comment's thread. Return to all 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.