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.
- Prepare
- Algorithms
- Graph Theory
- Even Tree
- Discussions
Even Tree
Even Tree
Sort by
recency
|
277 Discussions
|
Please Login in order to post a comment
A simple C++ solution using Depth First Search. The underlying principle is that you may cut an edge if and only if a subtree below that edge has an even number of nodes. We can calculate the number of nodes in a subtree for each node using recursion. If for any given node that number is even, we can cut the edge connecting the node to that subtree.
Just count the subtree size of each node and if it contains even nodes including itself, increment the count. It indicates it should have a cut. Below is the java code
Here's my Python code. I broke it down into three parts which made it a lot easier for me to think through. If testing my code, make sure to add "from queue import Queue"