Given a tree of N nodes, the task is to find the node having maximum depth starting from the root node, taking the root node at zero depth. If there are more than 1 maximum depth node, then find the one having the smallest value.
Examples:
Input:
1
/ \
2 3
/ \
4 5
Output: 4
Explanation:
For this tree:
Height of Node 1 - 0,
Height of Node 2 - 1,
Height of Node 3 - 1,
Height of Node 4 - 2,
Height of Node 5 - 2.
Hence, the nodes whose height is
maximum are 4 and 5, out of which
4 is minimum valued.
Input:
1
/
2
/
3
Output: 3
Explanation:
For this tree:
Height of Node 1 - 0,
Height of Node 2 - 1,
Height of Node 3 - 2
Hence, the node whose height
is maximum is 3.
Approach:
- The idea is to use Depth First Search(DFS) on the tree and for every node, check the height of every node as we move down the tree.
- Check if it is the maximum so far or not and if it has a height equal to the maximum value, then is it the minimum valued node or not.
- If yes then update the maximum height so far and the node value accordingly.
Below is the implementation of the above approach:
C++
// C++ implementation of for// the above problem#include <bits/stdc++.h>using namespace std;#define MAX 100000vector<int> graph[MAX + 1];// To store the height of each nodeint maxHeight, minNode;// Function to perform dfsvoid dfs(int node, int parent, int h){ // Store the height of node int height = h; if (height > maxHeight) { maxHeight = height; minNode = node; } else if (height == maxHeight && minNode > node) minNode = node; for (int to : graph[node]) { if (to == parent) continue; dfs(to, node, h + 1); }}// Driver codeint main(){ // Number of nodes int N = 5; // Edges of the tree graph[1].push_back(2); graph[1].push_back(3); graph[2].push_back(4); graph[2].push_back(5); maxHeight = 0; minNode = 1; dfs(1, 1, 0); cout << minNode << "\n"; return 0;} |
Java
// Java implementation of for// the above problemimport java.util.*;class GFG{static final int MAX = 100000;@SuppressWarnings("unchecked")static Vector<Integer>[] graph = new Vector[MAX + 1];// To store the height of each nodestatic int maxHeight, minNode;// Function to perform dfsstatic void dfs(int node, int parent, int h){ // Store the height of node int height = h; if (height > maxHeight) { maxHeight = height; minNode = node; } else if (height == maxHeight && minNode > node) minNode = node; for(int to : graph[node]) { if (to == parent) continue; dfs(to, node, h + 1); }}// Driver codepublic static void main(String[] args){ // Number of nodes int N = 5; for(int i = 0; i < graph.length; i++) graph[i] = new Vector<Integer>(); // Edges of the tree graph[1].add(2); graph[1].add(3); graph[2].add(4); graph[2].add(5); maxHeight = 0; minNode = 1; dfs(1, 1, 0); System.out.print(minNode + "\n");}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation of for# the above problemMAX = 100000 graph = [[] for i in range(MAX + 1)] # To store the height of each nodemaxHeight = 0minNode = 0 # Function to perform dfsdef dfs(node, parent, h): global minNode, maxHeight # Store the height of node height = h if (height > maxHeight): maxHeight = height minNode = node elif (height == maxHeight and minNode > node): minNode = node for to in graph[node]: if to == parent: continue dfs(to, node, h + 1) # Driver codeif __name__=="__main__": # Number of nodes N = 5 # Edges of the tree graph[1].append(2) graph[1].append(3) graph[2].append(4) graph[2].append(5) maxHeight = 0 minNode = 1 dfs(1, 1, 0) print(minNode)# This code is contributed by rutvik_56 |
C#
// C# implementation of for// the above problemusing System;using System.Collections.Generic; public class GFG{ static readonly int MAX = 100000;static List<int>[] graph = new List<int>[MAX + 1]; // To store the height of each nodestatic int maxHeight, minNode; // Function to perform dfsstatic void dfs(int node, int parent, int h){ // Store the height of node int height = h; if (height > maxHeight) { maxHeight = height; minNode = node; } else if (height == maxHeight && minNode > node) minNode = node; foreach(int to in graph[node]) { if (to == parent) continue; dfs(to, node, h + 1); }} // Driver codepublic static void Main(String[] args){ for(int i = 0; i < graph.Length; i++) graph[i] = new List<int>(); // Edges of the tree graph[1].Add(2); graph[1].Add(3); graph[2].Add(4); graph[2].Add(5); maxHeight = 0; minNode = 1; dfs(1, 1, 0); Console.Write(minNode + "\n");}} // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript implementation of for the above problem let MAX = 100000; let graph = new Array(MAX + 1); // To store the height of each node let maxHeight, minNode; // Function to perform dfs function dfs(node, parent, h) { // Store the height of node let height = h; if (height > maxHeight) { maxHeight = height; minNode = node; } else if (height == maxHeight && minNode > node) minNode = node; for(let to = 0; to < graph[node].length; to++) { if (graph[node][to] == parent) continue; dfs(graph[node][to], node, h + 1); } } for(let i = 0; i < graph.length; i++) graph[i] = []; // Edges of the tree graph[1].push(2); graph[1].push(3); graph[2].push(4); graph[2].push(5); maxHeight = 0; minNode = 1; dfs(1, 1, 0); document.write(minNode + "</br>");// This code is contributed by decode2207.</script> |
Output:
4
Time Complexity: O(N), Where N is the total number of nodes
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
