Recent Tutorials and Articles
    HackerRank Solution: Even Tree
    Published on: 30th July 2016

    This tutorial provides Java solution to "Even Tree" challenge of HackerRank.

    Hackerrank Challenge Details


    Problem Statement:

    You are given a tree (a simple connected graph with no cycles). The tree has N nodes numbered from 1 to N.

    Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of vertices.

    Input Format:

    The first line of input contains two integers N and M. N is the number of vertices, and M is the number of edges. 
    The next M lines contain two integers ui and vi which specifies an edge of the tree.

    Output Format:

    Print the number of removed edge..

    Constraints:

    • 2 < N < 100

    Sample Input:

    10 9
    2 1
    3 1
    4 3
    5 2
    6 1
    7 2
    8 6
    9 8
    10 8

    Sample Output:

    2

    Explanation:

    On removing edges (1, 3) and (1, 6), we can get the desired result.

    Original tree:

    Decomposed tree:

    Solution Details


    Java Implementation:

    package com.saintech.allprogtutorials.hackerrank.algos;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    /**
     * @author Sain Technology Solutions
     * 
     * Solution to Problem - https://www.hackerrank.com/challenges/even-tree
     *
     */
    public class EvenTree {
    	
    	/**
    	 * Represents Node of the graph and contains the nodes that are attached to it. We may 
    	 * also have ids but emitted as array index is being used as node id.
    	 */
    	private static class Node<T> {
    		private final List<Node<T>> childNodes = new ArrayList<>();
    		
    		private void addChildNode(Node<T> node) {
    			this.childNodes.add(node);
    		}
    	}
    	
    	/**
    	 * Returns an array of integer containing below information about tree represented by input node:
    	 * 	- No of vertices 
    	 * 	- Edges removed to decompose tree into trees of even vertices
    	 */
    	private static int[] decomposeTree(Node<Integer> node) {
    		
    		int count = 0, edgesToRemove = 0;
    		for(Node<Integer> childNode : node.childNodes) {
    			// For each child node
    			// calls current method recursively
    			final int[] tmpMetadata = decomposeTree(childNode);
    			// Accumulates edgesToRemove in a local variable
    			edgesToRemove += tmpMetadata[1];
    			// Checks if returned count is even - if yes, increments edgesToRemove by 1 
    			// otherwise adds returned count to this method's count
    			if(tmpMetadata[0] % 2 == 0) {
    				edgesToRemove++;
    			} else {
    				count += tmpMetadata[0];
    			}
    		}
    		// Increments count since we are done with current node processing
    		count++;
    		//returns count for input node along with edges that can be removed to decompose the tree
    		return new int[]{count, edgesToRemove};
    	}
    	
    	public static void main(String[] args) {
    		final Scanner in = new Scanner(System.in);
    		final int N = in.nextInt();
    		final int M = in.nextInt();
    		
    		// Keeps all the nodes of tree in an array
    		final Node<Integer>[] treeNodes = (Node<Integer>[]) new Node[N];
    		for(int i = 0; i < M; i++) {
    			// Gets first node of vertex
    			final int node1 = in.nextInt() - 1;
    			// Gets second node of vertex
    			final int node2 = in.nextInt() - 1;
    			
    			// If nodes exist in array, reuses those else creates a new node and adds back to array
    			treeNodes[node1] = (treeNodes[node1] == null ? new Node<Integer>() : treeNodes[node1]);
    			treeNodes[node2] = (treeNodes[node2] == null ? new Node<Integer>() : treeNodes[node2]);
    			
    			//In order to create edge, we need to link nodes. Since this is a tree, it will be a directed edge and
    			// for consistency, we will add bigger node to smaller nodes
    			if(node1 < node2) {
    				treeNodes[node1].addChildNode(treeNodes[node2]);
    			} else {
    				treeNodes[node2].addChildNode(treeNodes[node1]);
    			}
    		}
    		
    		// Since first element of array represents root of tree, we pass it to recursive method decompose tree
    		final int[] metadata = decomposeTree(treeNodes[0]);
    		
    		// Print no of edges to be removed returned by above method invocation
    		System.out.println(metadata[1]);
    		
    		in.close();
    	}
    }
    

    Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

    Published on: 30th July 2016