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<Integer> t_from,
                               List<Integer> t_to) {

    // Zip t_from and t_to in an array of edges.
    ArrayList<Edge> 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<Integer, Integer> nodeDimensions =
        evaluateNodeDimensions(t_nodes, edges);

    // Count the edges I can cut.
    int cutEdges = 0;
    for (Map.Entry<Integer, Integer> entry : nodeDimensions.entrySet()) {
      if (entry.getValue() % 2 == 1)
        continue;
      cutEdges++;
    }

    // -1 : not counting the root.
    return cutEdges - 1;
  }

  private static Map<Integer, Integer>
  evaluateNodeDimensions(int t_nodes, ArrayList<Edge> edges) {
    Map<Integer, Integer> 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 <fstream>
#include <iostream>
#include <vector>

struct node_data_t {
  int cuts;
  int childCount;
};

node_data_t even_nodes_impl(int nodeIdx, std::vector<int> const &t_from,
                            std::vector<int> 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<int> t_from, std::vector<int> 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<int> t_from(t_edges);
  std::vector<int> 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 <bits/stdc++.h>

using namespace std;

int main() {
  int n, m; cin >> n >> m;
  vector<vector<int>> 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<bool> visited(n);
  function<int(int)> 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.

tree 
We've worked on this challenge in these gyms: milan 
comments powered by Disqus