We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Tree Diameter

Number: 1177

Difficulty: Medium

Paid? Yes

Companies: Meta, TikTok, Apple, Google

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n-1) represented by an array of edges, determine the diameter of the tree, which is defined as the number of edges in the longest path in the tree.

Key Insights

  • The tree diameter is the longest path between any two nodes.
  • A two-pass DFS/BFS approach can be used:
    • First, pick an arbitrary node and find the farthest node from it.
    • Second, from that farthest node, compute the maximum distance to any other node.
  • This method works because the longest path of a tree always starts at a leaf and ends at a leaf.

Space and Time Complexity

Time Complexity: O(n) – Each node is visited once in each DFS/BFS pass.
Space Complexity: O(n) – The graph adjacency list and recursion/queue may hold up to n nodes.

Solution

We solve the problem using a two-pass depth-first search (DFS) approach. First, we start from an arbitrary node (e.g., node 0) and perform a DFS to locate the node farthest from it. Then, we perform a second DFS starting from this farthest node to compute the maximum distance to any other node, which is the tree's diameter. The tree is represented as an adjacency list, and the DFS tracks the current distance and the parent node to avoid cycles. This solution efficiently computes the desired result with a linear runtime relative to n, leveraging the tree structure properties.

Code Solutions

# Build the graph using an adjacency list.
def treeDiameter(edges):
    from collections import defaultdict
    graph = defaultdict(list)
    # Constructing the bidirectional graph.
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # DFS function that returns the farthest node and its distance.
    def dfs(node, parent, distance):
        farthest_node, max_distance = node, distance
        for neighbor in graph[node]:
            if neighbor != parent:
                candidate_node, candidate_distance = dfs(neighbor, node, distance + 1)
                if candidate_distance > max_distance:
                    farthest_node, max_distance = candidate_node, candidate_distance
        return farthest_node, max_distance
    
    # First DFS to find one endpoint of the diameter.
    farthest, _ = dfs(0, -1, 0)
    # Second DFS from the farthest node to determine the diameter.
    _, diameter = dfs(farthest, -1, 0)
    return diameter

# Example usage:
# edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
# print(treeDiameter(edges))  # Output should be 4
← Back to All Questions