Even Tree

So I recently came across this coding question on hackerrank and stackoverflow called Even Tree. The question goes as follows - 

You are given a tree (a simple connected graph with no cycles). You have to remove asmany edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.

To accomplish this, you will remove some edges from the tree. Find out the number of removed edges.

So the question requires us to traverse a tree and cutoff edges such that each sub-tree/forest created has even number of nodes. You can also treat this question as a directional graph question wherein you start from a node and remove any edges to come up with subgraphs that contain even number of nodes.

To make it easy to visualize, lets consider a tree -

                                    Fig 1 - Sample tree with all it edges

                            Fig 2 - Tree with edges to be removed marked in blue

Algorithm :-

• Populate the children below each node:- 

This step relies on the way the input is given for the problem(upper nodes being nearer to the root and lower nodes being the leaves. If the input is given out of order, I recommend using a level order traversal and do a bottom-up approach for this step to calculate the children below. The function populateChildren adds the number below each to a map and as we traverse bottom to top, we keep adding the number of children of each node in a node's adjacency list to that node's number of children.

• Traverse each edge and decide if it needs to be removed based on the number of children below each of the vertices connected through that edge:- 

This step iterates through all edges and checks if an edge needs to be removed. There are two cases when an edge can be removed 

- The first case is when the difference between the number of children below the parent node and the child node in the edge is odd AND the number of children below the child is odd. (The difference means that child node of the edge along with its children aggregate to an even number and the parent can get into a different forest of nodes. For example, consider the edge joining nodes 2 and 5. As 5 has odd number of children and difference between the children of parent and node is also odd indicating that the parent can find a different group with its children or its parent or both.)

- The second case is the case when children below both parent and child of an edge have an odd number, it is safe to remove that edge to get forests of even nodes.(For example, consider the edge joining nodes 1 and 3. For node 3, the number of children is three and for node 1, the number of children is nine. So node 1 will be able to connect to the remaining 5 nodes in such a way so as to make a forest of even nodes)

A sample input for this solution is as below :-

 30 29

 2 1

 3 2

 4 3

 5 2

 6 4

 7 4

 8 1

 9 5

 10 4

 11 4

 12 8

 13 2

 14 2

 15 8

 16 10

 17 1

 18 17

 19 18

 20 4

 21 15

 22 20

 23 2

 24 12

 25 21

 26 17

 27 5

 28 27

 29 4

 30 25

In the input, the first line indicates the number of vertices and edges respectively and the following lines indicate the edges connecting the nodes.

Pasting the solution code in Java below :-

1:  import java.util.ArrayList;  
2:  import java.util.HashMap;  
3:  import java.util.Map;  
4:  import java.util.Scanner;  
5:    
6:  class EvenTree {  
7:      private int numVertices = 0;  
8:      private int edges = 0;  
9:      private Map<Integer, Integer> edgeListMap = new HashMap<Integer, Integer>();  
10:      private Map<Integer, ArrayList<Integer>> adjListMap = new HashMap<Integer, ArrayList<Integer>>();  
11:      private Map<Integer, Integer> numChildren = new HashMap<Integer, Integer>();  
12:    
13:      //Method to decide which edges to remove  
14:      private void eliminateEdges() {  
15:          int edgesRemoved = 0;  
16:          for (Map.Entry<Integer, Integer> entry : edgeListMap.entrySet()) {  
17:              if (((this.numChildren.get(entry.getValue()) - this.numChildren  
18:                      .get(entry.getKey())) % 2 != 0 && this.numChildren  
19:                      .get(entry.getKey()) % 2 != 0)  
20:                      || (this.numChildren.get(entry.getValue()) % 2 != 0 && this.numChildren  
21:                              .get(entry.getKey()) % 2 != 0)) {  
22:                  // For printing the edges removed  
23:                  //System.out.println(entry.getKey() + ":" + entry.getValue());  
24:                  ++edgesRemoved;  
25:              }  
26:          }  
27:          System.out.println(edgesRemoved);  
28:      }  
29:    
30:      //Method to populate the number of children below each node  
31:      private void populateChildren() {  
32:          for (int i = numVertices; i > 0; i--) {  
33:              int numChildren = 0;  
34:              ArrayList<Integer> adjList = this.adjListMap.get(new Integer(i));  
35:              if (adjList != null) {  
36:                  for (Integer node : adjList) {  
37:                      if (this.numChildren.containsKey(node)) {  
38:                          numChildren = numChildren + 1  
39:                                  + this.numChildren.get(node);  
40:                      } else  
41:                          ++numChildren;  
42:                  }  
43:              }  
44:              this.numChildren.put(i, numChildren);  
45:          }  
46:      }  
47:    
48:      public static void main(String[] args) {  
49:    
50:          Scanner ob = new Scanner(System.in);  
51:          EvenTree eventree = new EvenTree();  
52:          eventree.numVertices = ob.nextInt();  
53:          if (eventree.numVertices % 2 != 0) {  
54:              System.out.println("Number of vertices are not even. Exiting...");  
55:              return;  
56:          }  
57:          eventree.edges = ob.nextInt();  
58:          int vertex1, vertex2;  
59:          for (int i = 0; i < eventree.edges; i++) {  
60:              vertex1 = ob.nextInt();  
61:              vertex2 = ob.nextInt();  
62:              eventree.edgeListMap.put(vertex1, vertex2);  
63:              if (eventree.adjListMap.containsKey(vertex2)) {  
64:                  ArrayList<Integer> adjListMap = eventree.adjListMap  
65:                          .get(vertex2);  
66:                  adjListMap.add(vertex1);  
67:              } else {  
68:                  ArrayList<Integer> adjList = new ArrayList<Integer>();  
69:                  adjList.add(vertex1);  
70:                  eventree.adjListMap.put(vertex2, adjList);  
71:              }  
72:          }  
73:      //Populate the children map  
74:          eventree.populateChildren();  
75:      //Decide the edges to be removed  
76:          eventree.eliminateEdges();  
77:      }  
78:  }  

The time complexity of this solution is O(V + E).