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
|
280 Discussions
|
Please Login in order to post a comment
Approach
Solution
Here is the PHP code:
Explanation:
$subtreeSize
array.This solution assumes that the tree is given in a 1-based index as in the example. If your tree nodes are 0-based, you should adjust the code accordingly.
C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star)
Cut each edge and check if the resulting subtree is even in length
This line should be added in the description very clearly
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.