Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 📃
2.
Problem Statement ❕
2.1.
Example 📑
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation 
3.
Solution 💡 
3.1.
C++ Implementation 📌
3.2.
Python Implementation 📌
3.2.1.
Output
3.3.
Complexities 📈
3.3.1.
Time Complexity ⏳
3.3.2.
Auxiliary Space Complexity 💾
4.
Frequently Asked Questions
4.1.
What is a graph?
4.2.
What is a tree?
4.3.
What is the height of a tree?
4.4.
What are a root and a leaf node in a tree?
4.5.
Why do we calculate the complexities of a program?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Find the Roots of a Tree that gives Minimum Height

Author Teesha Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction 📃

Tree is a data structure similar to a graph that stores data hierarchically. A tree is an undirected acyclic graph. Each tree has a root node and edges that connect the root node with its child nodes.

Find the Roots of a Tree that gives Minimum Height

This article will discuss the algorithm and implementation to find the roots of a tree that gives the minimum height.

Problem Statement ❕

You are given an undirected acyclic graph; you need to find the root for which the tree's height is minimum. You can consider any graph node as the tree's root node and find the root for which the height is minimum. If more than one root node minimizes the height, then return all those nodes.

Problem Statement

Example 📑

Input

Example input

Output

0

Explanation 

We see from the diagrams below that when each node is considered as the root node, the minimum height is found to be 2 when 0 is considered the root node. Hence the output is 0.

Explanation 1

Explanation 2

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

Solution 💡 

The solution to the problem is to find the longest path between two leaf nodes. The middle node of such a path will give us the node that, when taken as the root node, will have the minimum height. We can find the longest path; if the number of nodes is even, there will be two central nodes, hence two nodes with minimum height. But if the number of nodes is odd, only one node will have the minimum height. 

Solution Approach

The algorithm of the solution is given below: 

  • Initialize and declare a graph for which you need to find the roots of a tree that gives minimum height.
  • Use an adjacency list to represent the edges of a graph. Maintain a degree vector to keep track of the degree of each node of the graph.
  • Initialize a queue and enqueue all the leaf nodes to it. Delete those nodes from the graph.
  • At max, there can be two vertices with minimum height, so loop until you have two vertices. 
    • Consider each node from the queue once.
    • Decrement the degree of each neighbor of the current node. Enqueue the neighbor in the queue if it becomes a leaf node.
    • At last, the queue will have one or two nodes, our result.
  • Print the results. 

C++ Implementation 📌

#include <bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;

/* Graph class is used to create a graph and represent edges as an adjacency list */
class Graph
{
    public:
        int num_of_vertices;
   
        /* Initializing a pointer for adjacency list */
        vector<int> *adj;
        vector<int> degree;
   
        /* Declaring Constructor of the class */
        Graph(int num)
        {
            /* Initializing important variables */
            this->num_of_vertices = num;
            adj = new vector<int>[num_of_vertices];
           
            /* Initializing the degree of each node as 0 */
            for (int i = 0; i < num_of_vertices; i++)
                degree.push_back(0);
        }    

        /* Helper function to add an edge to the graph */
        void AddEdge(int v1, int v2)
        {
            /* adding the edge in adjacency list*/
            adj[v1].push_back(v2);
            adj[v2].push_back(v1);
           
            /* Incrementing the degree of both vertices by 1 */
            degree[v1]++;        
            degree[v2]++;        
        }
       
        /* Function to find the roots of a tree with minimum weight */
        vector<int> MinimumHeight()
        {
            queue<int> q;
         
            /* Add all the leaf nodes to the queue */
            for (int iter = 0; iter < num_of_vertices; iter++)
                if (degree[iter] == 1)
                    q.push(iter);
         
            /* At max, there can be two vertices with minimum height, so loop until you have two vertices */
            while (num_of_vertices > 2)
            {
                /* Already added some vertices to the queue, so remove those from the total vertices count.*/
                num_of_vertices = num_of_vertices - q.size();
               
                int tmp=q.size();
               
                for (int i = 0; i < tmp; i++)
                {
                    /* Consider each node in queue once */
                    int root = q.front();
                    q.pop();
                   
                    /* Decrement the degree of each neighbor of root and enqueue to the queue if it becomes a leaf node */
                    for (auto current_node = adj[root].begin(); current_node != adj[root].end(); current_node++)
                    {
                        degree[*current_node] -= 1;
                        if (degree[*current_node] == 1)
                            q.push(*current_node);
                    }
                }
            }
 
            /* Copy the answer to a vector */
            vector<int> roots;
            while (!q.empty())
            {
                roots.push_back(q.front());
                q.pop();
            }
           
            /* Returning the answer to the main function*/
            return roots;
        }
};
 
/* Driver Function */
int main()
{
    /* Initializing and Declaring the given graph*/
    Graph graph(6);
    graph.AddEdge(0, 1);
    graph.AddEdge(0, 3);
    graph.AddEdge(0, 4);
    graph.AddEdge(1, 2);
    graph.AddEdge(5, 3);
 
    /* Calling the Function to find the roots of a tree with minimum height and storing the result in roots variable*/
    vector <int> roots = graph.MinimumHeight();
   
    /* Printing the results*/
    for (int node = 0; node < roots.size(); node++)
        cout << roots[node] << " ";
       
    return 0;
}

Python Implementation 📌

from queue import Queue

'''Graph class is used to create a graph and represent edges as an adjacency list'''
class Graph:
   
    '''Declaring Constructor of the class'''
    def __init__(self, num_of_vertices):
        '''Intializing important structures '''
        self.num_of_vertices = num_of_vertices
        self.degree = [0 for i in range(num_of_vertices)]
        self.adj = dict((i, []) for i in range(num_of_vertices))
       
    '''Helper function to add an edge to the graph '''
    def AddEdge(self, v1, v2):
        '''adding the edge in adjacency list'''
        self.adj[v1].append(v2)
        self.adj[v2].append(v1)
           
        '''Incrementing the degree of both vertices by 1 '''
        self.degree[v1] += 1        
        self.degree[v2] += 1        
   
    ''' Function to find the roots of a tree with minimum height'''
    def MinimumHeight(self):
        q = Queue()
        
        '''Add all the leaf nodes to the queue'''
        for iter in range(self.num_of_vertices):
            if self.degree[iter] == 1:
                q.put(iter)
         
        '''At max, there can be two vertices with minimum height, so loop until you have two vertices. '''
        while (self.num_of_vertices > 2):
            ''' Already added some vertices to queue, so remove those from total vertices count.'''
            self.num_of_vertices = self.num_of_vertices - q.qsize()
           
            tmp = q.qsize()
               
            for i in range(tmp):
                ''' Consider each node in quere once '''
                root = q.get()
           
                '''Decrement the degree of each neighbor of root and enqueue to the queue if it becomes a leaf node'''
                for current_node in self.adj[root]:
                    self.degree[current_node] -= 1
                    if self.degree[current_node] == 1:
                        q.put(current_node)  
           
        '''Copy the answer to a vector'''
        roots = []
        while q.qsize() > 0:
            roots.append(q.get())
           
        ''' Returning the answer to the main function'''
        return roots

''' Driver Function '''
def main():

    ''' Initializing and Declaring the given graph'''
    graph = Graph(6);
    graph.AddEdge(0, 1);
    graph.AddEdge(0, 3);
    graph.AddEdge(0, 4);
    graph.AddEdge(1, 2);
    graph.AddEdge(5, 3);
 
    ''' Calling the Function to find the roots of a tree with minimum height and storing the result in roots variable'''
    roots = graph.MinimumHeight();
   
    ''' Printing the results'''
    for root in roots:
        print(root, end = ' ')
       
'''Executing Main'''
main()

Output

0

Complexities 📈

Time Complexity 

O(N), Where N denotes the count of nodes in the tree. 

Reason:  The time complexity is O(N) because we consider each node only once. 

Auxiliary Space Complexity 💾

O(N+ K), where N denotes the count of nodes in the graph and K denotes the number of edges.

Reason: We are using an adjacency list to represent the graph, which takes O(N+K) additional space. Other than this, the vector to store the degree of each node and the queue is also used with can take a maximum of N elements at a time. So Auxiliary space complexity of the above program is O(N+K) + O(N) + O(N), which is equal to O(N+K).

Frequently Asked Questions

What is a graph?

A graph is a data structure used to represent highly correlated data. A graph is made up of vertices and edges. The edges are used to connect the vertices based on some relationship.

What is a tree?

A Tree is a non-linear data structure similar to a graph that stores data hierarchically. A tree is an undirected graph with no cycles. Each tree has a root node and edges that connect the root node with its child nodes.

What is the height of a tree?

The height of a tree is referred to as the length of the path of the furthest leaf node from the tree's root. In order words, it is also given by the number of levels present in the tree.

What are a root and a leaf node in a tree?

The root node of a tree is the master node with which the tree begins. It has no incoming edges. The leaf node or terminal node is the child node of a tree that does not have any child. The outdegree of such nodes is 0. 

Why do we calculate the complexities of a program?

Complexities of a program are used to compare two or more approaches to solve the same problem. It provides a measure to compare and find a more efficient solution in terms of time and space.

Conclusion

This article discussed the algorithm and implementation to find the roots of a tree that gives minimum height. To learn more about tree data structure, visit, Introduction to Trees - Coding Ninjas Coding Ninjas Studio

I hope you would have gained a better understanding of these topics now!

Check out this problem - Check If A String Is Palindrome

Are you planning to ace the interviews with reputed product-based companies like AmazonGoogleMicrosoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!
 

Happy Coding!

Previous article
Find palindromic path of given length K in a complete Binary Weighted Graph
Next article
Maximize Difference between pair of Nodes in a given rooted Tree such that one Node is Ancestor of another
Live masterclass