FastPrep
Problem · Tree

Find Min Distance to Furthest Node (Google Tokyo)

Learn this problem
● MediumGoogleINTERNOA
See Google hiring insights

Problem statement

You are given a tree-shaped undirected graph consisting of n nodes labeled 1...n and n-1 edges. The i-th edge connects nodes edges[i][0] and edges[i][1] together.

For a node x in the tree, let d(x) be the distance (the number of edges) from x to its farthest node. Find the min value of d(x) for the given tree.

The tree has the following properties:

  • It is connected.
  • It has no cycles.
  • For any pair of distinct nodes x and y in the tree, there's exactly 1 path connecting x and y.

    • Function

    findMinDistanceToFurthestNode(n: int, edges: int[][]) → int

    Complete the function findMinDistanceToFurthestNode in the editor.

    findMinDistanceToFurthestNode has the following parameters:

    1. int n: the number of nodes
    2. int edges[n-1][2]: an array of n-1 edges where each edges[i] contains two integers representing an edge connecting the nodes

    Returns

    int: the minimum distance to the furthest node

    Examples

    Example 1

    n = 6edges = [[1, 4], [2, 3], [3, 4], [4, 5], [5, 6]]return = 2
    Example 1 illustration
    No explanation available.

    Example 2

    n = 6edges = [[1, 3], [4, 5], [5, 6], [3, 2], [3, 4]]return = 2
    Example 2 illustration
    No explanation available.

    Example 3

    n = 2edges = [[1, 2]]return = 1
    Example 3 illustration
    No explanation available.

    Example 4

    n = 10edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10]]return = 5
    Example 4 illustration
    No explanation available.

    Example 5

    n = 10edges = [[7, 8], [7, 9], [4, 5], [1, 3], [3, 4], [6, 7], [4, 6], [2, 3], [9, 10]]return = 3
    Example 5 illustration
    No explanation available.

    Constraints

    • 1 <= n <= 10^5
    • edges.length == n - 1
    • Every edge joins two distinct labels in [1, n], and the graph is a tree.

    More Google problems

    drafts saved locally
    public int findMinDistanceToFurthestNode(int n, int[][] edges) {
    // write your code here
}
    n6
    edges[[1, 4], [2, 3], [3, 4], [4, 5], [5, 6]]
    expected2
    checking account