Minimum valued node having maximum depth in an N-ary Tree

0 0 4 minutes read

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 100000
 
vector<int> graph[MAX + 1];
 
// To store the height of each node
int maxHeight, minNode;
 
// Function to perform dfs
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 code
int 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 problem
import 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 node
static int maxHeight, minNode;
 
// Function to perform dfs
static 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 code
public 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 problem
MAX = 100000
  
graph = [[] for i in range(MAX + 1)]
  
# To store the height of each node
maxHeight = 0
minNode = 0
  
# Function to perform dfs
def 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 code
if __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 problem
using 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 node
static int maxHeight, minNode;
  
// Function to perform dfs
static 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 code
public 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:

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 zambiatek!