Minimum of the Maximum distances from any node to all other nodes of given Tree

Namachila November 19, 2025

0 1 6 minutes read

Given a tree with N vertices and N-1 edges represented by a 2D array edges[], the task is to find the minimum value among the maximum distances from any node to all other nodes of the tree.

Examples:

Input: N = 4, edges[] = { {1, 2}, {2, 3}, {2, 4} }
Output: 1
Explanation: The Tree looks like the following.
2
/ | \
1 3 4
Maximum distance from house number 1 to any other node is 2.
Maximum distance from house number 2 to any other node is 1.
Maximum distance from house number 3 to any other node is 2.
Maximum distance from house number 4 to any other node is 2.
The minimum among these is 1.

Input: N = 10, edges[] = { {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 8}, {8, 9}, {9, 10} }
Output: 5

Approach: This problem can be solved using Depth First Search based on the following idea:

For each node find the farthest node and the distance to that node. Then find the minimum among those values.

Follow the steps mentioned below to implement the idea:

Create a distance array (say d[]) where d[i] stores the maximum distance to all other nodes from the i^th node.
For every node present in the tree consider each of them as the source one by one:
- Mark the distance of the source from the source as zero.
- Find the maximum distance of all other nodes from the source.
Find the minimum value among these maximum distances.

Below is the implementation of the above approach:

C++

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to run DFS
void dfs(vector<int>& d, int node,
         vector<vector<int> >& adj, int dist)
{
    d[node] = dist;
 
    // DFS call for all its neighbours
    for (auto child : adj[node]) {
        if (dist + 1 < d[child])
            dfs(d, child, adj, dist + 1);
    }
}
 
// Function to find the minimum distance
int minDist(int N, vector<vector<int> >& edges)
{
    int ans = INT_MAX;
 
    // Creation of the adjacency matrix
    vector<vector<int> > adj(N + 1);
    for (auto u : edges) {
        adj[u[0]].push_back(u[1]);
        adj[u[1]].push_back(u[0]);
    }
 
    // Consider ith node as source
    // in each iteration
    for (int i = 1; i <= N; i++) {
 
        // Distance array to store
        // distance of all the nodes
        // from source
        vector<int> d(N + 1, INT_MAX);
 
        // DFS traversal of the tree and store
        // distance of all nodes from source
        dfs(d, i, adj, 0);
 
        int dist = 0;
 
        // Find max distance from distance array
        for (int j = 1; j <= N; j++)
            dist = max(dist, d[j]);
 
        // If distance found is smaller than ans
        // then make ans equal to distance
        ans = min(ans, dist);
    }
 
    // Return the minimum value
    return ans;
}
 
// Driver Code
int main()
{
    int N = 4;
    vector<vector<int> > edges
        = { { 1, 2 }, { 2, 3 }, { 2, 4 } };
 
    // Function call
    cout << minDist(N, edges);
    return 0;
}

Java

// Java code to implement the above approach
 
import java.util.ArrayList;
 
public class GFG {
 
    // Function to run DFS
    static void dfs(int[] d, int node,
                    ArrayList<Integer>[] adj, int dist)
    {
        d[node] = dist;
 
        // DFS call for all its neighbours
        for (int child : adj[node]) {
            if (dist + 1 < d[child])
                dfs(d, child, adj, dist + 1);
        }
    }
 
    // Function to find the minimum distance
    @SuppressWarnings("unchecked")
    static int minDist(int N, int[][] edges)
    {
        int ans = Integer.MAX_VALUE;
 
        // Creation of the adjacency matrix
        ArrayList<Integer>[] adj = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++)
            adj[i] = new ArrayList<Integer>();
 
        for (int[] u : edges) {
            adj[u[0]].add(u[1]);
            adj[u[1]].add(u[0]);
        }
 
        // Consider ith node as source
        // in each iteration
        for (int i = 1; i <= N; i++) {
 
            // Distance array to store
            // distance of all the nodes
            // from source
            int[] d = new int[N + 1];
            for (int j = 0; j <= N; j++)
                d[j] = Integer.MAX_VALUE;
 
            // DFS traversal of the tree and store
            // distance of all nodes from source
            dfs(d, i, adj, 0);
 
            int dist = 0;
 
            // Find max distance from distance array
            for (int j = 1; j <= N; j++)
                dist = Math.max(dist, d[j]);
 
            // If distance found is smaller than ans
            // then make ans equal to distance
            ans = Math.min(ans, dist);
        }
 
        // Return the minimum value
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 4;
        int[][] edges = { { 1, 2 }, { 2, 3 }, { 2, 4 } };
 
        // Function call
        System.out.println(minDist(N, edges));
    }
}
 
// This code is contributed by Lovely Jain

Python3

# Python code to implement the above approach
 
# Function to run DFS
import sys
 
def dfs(d, node, adj, dist):
    d[node] = dist
 
    # DFS call for all its neighbours
    for child in adj[node]:
        if (dist + 1 < d[child]):
            dfs(d, child, adj, dist + 1)
     
# Function to find the minimum distance
def minDist(N, edges):
    ans = sys.maxsize
 
    # Creation of the adjacency matrix
    adj = [[] for i in range(N+1)]
    for u in edges:
        adj[u[0]].append(u[1])
        adj[u[1]].append(u[0])
     
    # Consider ith node as source
    # in each iteration
    for i in range(1,N+1):
 
        # Distance array to store
        # distance of all the nodes
        # from source
        d = [sys.maxsize for i in range(N+1)]
 
        # DFS traversal of the tree and store
        # distance of all nodes from source
        dfs(d, i, adj, 0)
        dist = 0
 
        # Find max distance from distance array
        for j in range(1,N+1):
            dist = max(dist, d[j])
 
        # If distance found is smaller than ans
        # then make ans equal to distance
        ans = min(ans, dist)
 
    # Return the minimum value
    return ans
 
# Driver Code
N = 4
edges = [[1, 2], [2, 3], [2, 4]]
 
# Function call
print(minDist(N, edges))
 
# This code is contributed by shinjanpatra

C#

// C# code to implement the above approach
 
using System;
using System.Collections;
using System.Collections.Generic;
 
public class GFG {
 
    // Function to run DFS
    static void dfs(int[] d, int node, List<int>[] adj,
                    int dist)
    {
        d[node] = dist;
 
        // DFS call for all its neighbours
        foreach(int child in adj[node])
        {
            if (dist + 1 < d[child])
                dfs(d, child, adj, dist + 1);
        }
    }
 
    // Function to find the minimum distance
    static int minDist(int N, int[, ] edges)
    {
        int ans = Int32.MaxValue;
 
        // Creation of the adjacency matrix
        List<int>[] adj = new List<int>[ N + 1 ];
        for (int i = 0; i <= N; i++)
            adj[i] = new List<int>();
 
        for (int i = 0; i < edges.GetLength(0); i++) {
            int[] u = { edges[i, 0], edges[i, 1] };
            adj[u[0]].Add(u[1]);
            adj[u[1]].Add(u[0]);
        }
 
        // Consider ith node as source
        // in each iteration
        for (int i = 1; i <= N; i++) {
 
            // Distance array to store
            // distance of all the nodes
            // from source
            int[] d = new int[N + 1];
            for (int j = 0; j <= N; j++)
                d[j] = Int32.MaxValue;
 
            // DFS traversal of the tree and store
            // distance of all nodes from source
            dfs(d, i, adj, 0);
 
            int dist = 0;
 
            // Find max distance from distance array
            for (int j = 1; j <= N; j++)
                dist = Math.Max(dist, d[j]);
 
            // If distance found is smaller than ans
            // then make ans equal to distance
            ans = Math.Min(ans, dist);
        }
 
        // Return the minimum value
        return ans;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 4;
        int[, ] edges = { { 1, 2 }, { 2, 3 }, { 2, 4 } };
 
        // Function call
        Console.WriteLine(minDist(N, edges));
    }
}
 
// This code is contributed by karandeep1234.

Javascript

<script>
// Javascript code to implement the above approach
 
// Function to run DFS
function dfs(d, node, adj, dist) {
    d[node] = dist;
 
    // DFS call for all its neighbours
    for (let child of adj[node]) {
        if (dist + 1 < d[child])
            dfs(d, child, adj, dist + 1);
    }
}
 
// Function to find the minimum distance
function minDist(N, edges) {
    let ans = Number.MAX_SAFE_INTEGER;
 
    // Creation of the adjacency matrix
    let adj = new Array(N + 1).fill(0).map(() => new Array());
    for (let u of edges) {
        adj[u[0]].push(u[1]);
        adj[u[1]].push(u[0]);
    }
 
    // Consider ith node as source
    // in each iteration
    for (let i = 1; i <= N; i++) {
 
        // Distance array to store
        // distance of all the nodes
        // from source
        let d = new Array(N + 1).fill(Number.MAX_SAFE_INTEGER);
 
        // DFS traversal of the tree and store
        // distance of all nodes from source
        dfs(d, i, adj, 0);
 
        let dist = 0;
 
        // Find max distance from distance array
        for (let j = 1; j <= N; j++)
            dist = Math.max(dist, d[j]);
 
        // If distance found is smaller than ans
        // then make ans equal to distance
        ans = Math.min(ans, dist);
    }
 
    // Return the minimum value
    return ans;
}
 
// Driver Code
let N = 4;
let edges = [[1, 2], [2, 3], [2, 4]];
 
// Function call
document.write(minDist(N, edges));
 
// This code is contributed by gfgking.
</script>

Output

Time Complexity: O(N*N)
Auxiliary Space: O(N)

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!