Convert a tree to forest of even nodes

Introduction

In this blog, we will discuss the approach to finding the maximum number of edges that can be removed from the tree to obtain a forest of trees having an even number of nodes at last. Before jumping on the approach to the problem, let us first understand the problem.

Problem Statement

Given a tree having an even number of nodes,we need to find the maximum number of edges to be removed from the tree so that a forest is obtained having an even number of nodes in the end.Note that the solution always exists because the initial number of nodes given is even.

Sample Example

Input: 

Output: 

The dotted lines represent the removed edges. Any further removal of edges will not satisfy the condition of even nodes.

Approach

This approach aims to find the subtrees having an even number of edges and remove the subtree from the tree. This will ensure the even condition of the number of nodes as the initially given number of trees is even. We will be using Depth First Search to traverse the tree.

Algorithm

Step 1: Implement a DFS Algorithm function with return type as int since this will return the number of nodes in the subtree.

Step 2: Traverse the adjacency list inside the dfs function to find the unvisited nodes.

Step 3: For each nonvisited node, find the number of nodes in the subtree of subtree.

Step 4: Do the following according to the number of nodes found:

1. If the number of nodes in the subtree is found to be even, then increment the number of edges to be removed.
2. Else leave the subtree as a child of the current node.

Implementation

C++

#include<bits/stdc++.h>
Using namespace std;

//function for dfs traversal and finding the number of nodes in the subtree
int dfs(int node,int *ans,vector<int> tree[12],int visited[12]){
    int total_count = 0,count = 0;
    
    //mark the current node as visited
    Visited[node] = 1;
    
    //traversing the adjacent nodes
    for(int i = 0;i < tree[node].size();i++){
    
        //check if current node is visited or not
        if(visited[tree[node][i]] == 0){
        
            //store the count of nodes in the count variable
            count = dfs(tree[node][i],ans,tree,visited);
            
            //if count is even then increment the number of edges to be removed else leave it as it is
            (count%2)?(total_count += count):((*ans)++);
        }
    }
    return total_count+1;
}

int main(){
    vector<int> tree[12];
    
    tree[1].push_back(2);
    tree[2].push_back(1);
    
    tree[1].push_back(3);
    tree[3].push_back(1);

    tree[1].push_back(4);
    tree[4].push_back(1);

    tree[2].push_back(5);
    tree[5].push_back(2);

    tree[2].push_back(6);
    tree[6].push_back(2);

    tree[3].push_back(7);
    tree[7].push_back(3);

    tree[4].push_back(8);
    tree[8].push_back(4);

    tree[8].push_back(9);
    tree[9].push_back(8);

    tree[8].push_back(10);
    tree[10].push_back(8);

    int visited[12];
    memset(visited,0,sizeof(visited));
    int ans = 0;
    //calling the dfs traversal function
    dfs(1,ans,tree,visited);
    //print the maximum tree in the forest which satisfies the condition
    cout<<ans<<endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output: 

2

Complexity Analysis

Time Complexity: O(n)

Since the approach uses a dfs traversal which has a time complexity of O(V+E), here both V and E are in order of n, therefore the overall time complexity of the approach O(n).

Space Complexity: O(1)

As no extra space is required apart from the given space, therefore overall space complexity is of order O(1).
Check out this problem - Largest BST In Binary Tree