# Even Tree

See the original problem on HackerRank.

## Solutions

One solution: traverse the tree once to evaluate the size (i.e. the number of nodes) of each subtree; then, traverse the tree one more time and count the subtrees with even size.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  package src; import java.util.*; public class EvenForest { private record Edge(int from, int to) {} public static int evenForest(int t_nodes, int t_edges, List t_from, List t_to) { // Zip t_from and t_to in an array of edges. ArrayList edges = new ArrayList<>(); for (int i = 0; i < t_edges; i++) { int from = t_from.get(i); int to = t_to.get(i); edges.add(new Edge(Math.max(from, to), Math.min(from, to))); } edges.sort(Comparator.comparingInt((Edge edge) -> edge.from).reversed()); // Evaluate the size of each subtree. Map nodeDimensions = evaluateNodeDimensions(t_nodes, edges); // Count the edges I can cut. int cutEdges = 0; for (Map.Entry entry : nodeDimensions.entrySet()) { if (entry.getValue() % 2 == 1) continue; cutEdges++; } // -1 : not counting the root. return cutEdges - 1; } private static Map evaluateNodeDimensions(int t_nodes, ArrayList edges) { Map nodeDimensions = new HashMap<>(t_nodes); for (Edge edge : edges) { int fromNode = edge.from; int toNode = edge.to; nodeDimensions.put(fromNode, nodeDimensions.getOrDefault(fromNode, 1)); nodeDimensions.put(toNode, nodeDimensions.getOrDefault(toNode, 1) + nodeDimensions.get(fromNode)); } return nodeDimensions; } } 

We can also solve the problem with a single traversal, even though this doesn’t change the algorithmic complexity of the solution. The idea is to adopt a bottom-up approach: we keep the count of how many children the current node has while performing a depth-first-search traversal. Whenever this count is even, we increment the number of cuts.

Here’s a possible recursive implementation in C++:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48  #include #include #include struct node_data_t { int cuts; int childCount; }; node_data_t even_nodes_impl(int nodeIdx, std::vector const &t_from, std::vector const &t_to) { node_data_t data{}; auto const edgeCount = t_from.size(); for (std::size_t e{}; e != edgeCount; ++e) { // Filter the children of nodeIdx if (t_to[e] == nodeIdx) { auto const childData = even_nodes_impl(t_from[e], t_from, t_to); auto const childTreeNodeCount = childData.childCount + 1; data.childCount += childTreeNodeCount; auto const canCut = childTreeNodeCount % 2 == 0; data.cuts += childData.cuts + canCut; } } return data; } int evenForest(int /*t_nodes (unused) */, int /* t_edges (unused) */, std::vector t_from, std::vector t_to) { return even_nodes_impl(1 /* root node is 1 */, t_from, t_to).cuts; } int main() { int t_nodes{}, t_edges{}; std::cin >> t_nodes >> t_edges; std::vector t_from(t_edges); std::vector t_to(t_edges); for (int i = 0; i != t_edges; ++i) std::cin >> t_from[i] >> t_to[i]; std::ofstream{std::getenv("OUTPUT_PATH")} << evenForest(t_nodes, t_edges, t_from, t_to) << '\n'; } 

The above solution is also easily implementable in Haskell:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61  module Main where import Control.Monad import Data.List import System.Environment import System.IO data Edge a = Edge {from :: a, to :: a} data Tree a = Tree {root :: a, edges :: [Edge a]} -- | Generate a Tree from t_to and t_from lists. mkTree :: (Integral a) => a -> [a] -> [a] -> Tree a mkTree root f t = Tree root $zipWith Edge f t -- | Implement @evenTree@ using @Edge@ and @Tree@ as more convenient data -- structures. evenTreeImpl :: (Eq a) => Tree a -> Int evenTreeImpl = fst . go where -- Traverse the tree and accumulate a pair representing the number of cuts -- and the number of children. go = foldl' acc (0, 0) . map go . rootSubtrees -- Get the 1-st level subtrees of the tree root. rootSubtrees (Tree r edges) = map ((Tree edges) . from) . filter ((== r) . to)$ edges -- Accumulate the cuts and children count from the child nodes with the -- current node. acc (cuts, children) (childCuts, childChildren) = -- If childChildren is odd, the subtree rooted at that child has an even -- number of nodes; thus, I can cut it. let canCut = odd childChildren newChildren = children + childChildren + 1 newCuts = cuts + childCuts + if canCut then 1 else 0 in (newCuts, newChildren) evenTree :: Int -> Int -> [[Int]] -> Int evenTree _ _ tree = case transpose tree of [froms, tos] -> evenTreeImpl $mkTree 1 froms tos -- We assume the input is correct. _ -> undefined main = do nmTemp <- getLine let readInt = read :: String -> Int nm = words nmTemp n = readInt (nm !! 0) m = readInt (nm !! 1) treeTemp <- replicateM m getLine let tree = (readInt <$>) . words <\$> treeTemp result = evenTree n m tree outputPath <- getEnv "OUTPUT_PATH" fptr <- openFile outputPath WriteMode hPrint fptr result hClose fptr 

Note that both in the C++ and Haskell solutions above, each time we traverse the children of a given node (in even_nodes_impl or rootSubtrees), we loop through all the edges, thus making these algorithms $$O(n^2)$$. This is fine under the current constrains (the number of edges is no greater than 100). For bigger trees, however, we may want to keep a hash map that associates each node to the list of its children. Assuming we had such a hash map, the algorithmic complexity of the two solutions above would be $$O(n)$$.

Even though the first solution uses an hash map to associate each node to its children, its algorithmic cost is $$O(n log n)$$ because of the sorting.

Attendees Alessio and Giulio provided sill another C++ solution based on a depth-first-search traversal:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28  #include using namespace std; int main() { int n, m; cin >> n >> m; vector> adj(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--, b--; adj[a].push_back(b); adj[b].push_back(a); } int ans = -1; vector visited(n); function dfs = [&](int node) -> int { visited[node] = true; int children = 0; for (auto neigh : adj[node]) if (!visited[neigh]) children += dfs(neigh) + 1; ans += children % 2; return children; }; dfs(0); cout << ans; } 

The main idea is that, if we find a subtree with an even size, we can cut it greedily from the graph. In fact, we know the remaining graph will still have an even size. So we can just count the number of such subtrees. For this solution we have

• $$O(n + e)$$ spacial complexity;
• $$O(n + e)$$ time complexity;

Since we have $$e = n - 1$$ for a tree, we’re left with $$O(n)$$ complexity in time an space.

We've worked on this challenge in these gyms: milan