Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a forest in computer science?
3.2.
What is the time complexity of DFS traversal?
3.3.
What is a Tree in computer science?
4.
Conclusion
Last Updated: Mar 27, 2024

Convert a tree to forest of even nodes

Author Ankit kumar
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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.

Convert a tree to forest of even nodes

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: 

Convert a tree to forest of even nodes input

Output: 

Convert a tree to forest of even nodes 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;
}

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a forest in computer science?

A forest is a set of one or more trees where all the trees follow some common configuration. It can be described as a group of trees.

What is the time complexity of DFS traversal?

The time complexity of a DFS traversal is O(V+E), where V is the number of vertices in the graph and E is the number of edges connecting the vertices.

What is a Tree in computer science?

A tree is a non-linear data structure consisting of nodes that store values and are connected by edges.

Conclusion

This blog discussed the approach to finding the maximum number of edges that can be removed from the tree to obtain a forest of trees with an even number of nodes.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!!