LeetCode 1245 - Tree Diameter

LeetCode Problem 1245

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

The problem asks us to find the diameter of a tree, which is defined as the number of edges in the longest path between any two nodes. We are given an undirected tree represented as a list of edges. Each edge connects two nodes, labeled from 0 to n - 1. The input array edges has n - 1 elements, which aligns with the property of a tree that a tree with n nodes always has exactly n - 1 edges.

The expected output is a single integer representing the longest path (in edges) between any two nodes in the tree. Importantly, the path does not have to pass through the root, since the tree is not necessarily rooted.

The constraints tell us the tree can be moderately large, up to 10,000 nodes, so algorithms with O(n²) complexity could be too slow. Each node pair in edges is unique, and there are no cycles, guaranteeing that the input is always a valid tree.

Important edge cases include a single-node tree, where the diameter should be 0 since there are no edges, or a linear chain, where the diameter is n - 1 edges.

Approaches

Brute Force

A brute-force approach would involve computing the longest path starting from every node. This can be done by performing a BFS or DFS from each node, tracking the longest distance to all other nodes. While this method works, it is inefficient because for n nodes, each DFS or BFS takes O(n) time, resulting in a total complexity of O(n²). For n up to 10⁴, this is prohibitively slow.

Optimal Approach

The key observation is that the diameter of a tree can be found by performing two BFS/DFS traversals. First, pick any arbitrary node and perform a DFS or BFS to find the farthest node from it, say u. Then perform another DFS or BFS starting from u to find the farthest node from u, say v. The distance between u and v is the diameter of the tree. This works because in a tree, the farthest node from any starting point is always an endpoint of the diameter path.

This approach reduces the complexity to O(n) for both time and space since we traverse each node at most twice and use adjacency lists to store edges.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	BFS/DFS from every node to find the longest path
Optimal	O(n)	O(n)	Two DFS/BFS traversals using adjacency list representation

Algorithm Walkthrough

1. Convert the edge list into an adjacency list to represent the tree. This allows efficient traversal of neighbors.
2. Choose an arbitrary starting node, for example, node 0.
3. Perform a DFS (or BFS) from the starting node to find the farthest node from it. Track both the distance and the node itself.
4. Once the farthest node is found (call it u), perform another DFS/BFS starting from u to find the farthest node from u. The distance to this node is the diameter.
5. Return the distance found in step 4.

Why it works: In any tree, the farthest node from an arbitrary node is guaranteed to be an endpoint of the longest path. By finding the farthest node from this endpoint, we ensure we measure the maximum path length in the tree. This guarantees correctness.

Python Solution

from typing import List, Tuple
from collections import defaultdict, deque

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        if not edges:
            return 0

        # Build adjacency list
        tree = defaultdict(list)
        for u, v in edges:
            tree[u].append(v)
            tree[v].append(u)

        # Helper function for BFS
        def bfs(start: int) -> Tuple[int, int]:
            visited = set()
            queue = deque([(start, 0)])
            farthest_node, max_dist = start, 0

            while queue:
                node, dist = queue.popleft()
                if dist > max_dist:
                    farthest_node, max_dist = node, dist
                visited.add(node)
                for neighbor in tree[node]:
                    if neighbor not in visited:
                        queue.append((neighbor, dist + 1))
                        visited.add(neighbor)
            return farthest_node, max_dist

        # First BFS to find one endpoint of the diameter
        u, _ = bfs(0)
        # Second BFS to find the actual diameter
        _, diameter = bfs(u)
        return diameter

The Python implementation first constructs the adjacency list for efficient neighbor lookup. The bfs function finds the farthest node and distance from a given start. The first BFS identifies one endpoint of the diameter, and the second BFS from that endpoint computes the longest path in the tree.

Go Solution

package main

func treeDiameter(edges [][]int) int {
    if len(edges) == 0 {
        return 0
    }

    // Build adjacency list
    n := len(edges) + 1
    tree := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        tree[u] = append(tree[u], v)
        tree[v] = append(tree[v], u)
    }

    // BFS helper
    bfs := func(start int) (int, int) {
        visited := make([]bool, n)
        queue := []struct {
            node, dist int
        }{{start, 0}}
        visited[start] = true
        farthestNode, maxDist := start, 0

        for len(queue) > 0 {
            curr := queue[0]
            queue = queue[1:]
            if curr.dist > maxDist {
                farthestNode, maxDist = curr.node, curr.dist
            }
            for _, neighbor := range tree[curr.node] {
                if !visited[neighbor] {
                    visited[neighbor] = true
                    queue = append(queue, struct {
                        node, dist int
                    }{neighbor, curr.dist + 1})
                }
            }
        }
        return farthestNode, maxDist
    }

    u, _ := bfs(0)
    _, diameter := bfs(u)
    return diameter
}

In Go, the adjacency list is represented as a slice of slices. The BFS uses a slice as a queue and a visited boolean slice. Other than syntax differences, the algorithm logic is identical to the Python version.

Worked Examples

Example 1: edges = [[0,1],[0,2]]

1. Build adjacency list: {0: [1,2], 1: [0], 2: [0]}
2. BFS from 0 finds farthest node 1 (distance 1)
3. BFS from 1 finds farthest node 2 (distance 2)
4. Return 2

Example 2: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]

1. Adjacency list: {0:[1],1:[0,2,4],2:[1,3],3:[2],4:[1,5],5:[4]}
2. BFS from 0 finds farthest node 3 (distance 3)
3. BFS from 3 finds farthest node 5 (distance 4)
4. Return 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Two BFS traversals, each visits every node once
Space	O(n)	Adjacency list + BFS queue + visited set

The time complexity is linear since each node and edge is visited at most twice. Space complexity is dominated by the adjacency list and auxiliary structures used in BFS.

Test Cases

# provided examples
assert Solution().treeDiameter([[0,1],[0,2]]) == 2  # simple three-node tree
assert Solution().treeDiameter([[0,1],[1,2],[2,3],[1,4],[4,5]]) == 4  # larger tree

# single node
assert Solution().treeDiameter([]) == 0  # diameter of single-node tree

# linear chain
assert Solution().treeDiameter([[0,1],[1,2],[2,3],[3,4]]) == 4  # path length equals n-1

# star shaped tree
assert Solution().treeDiameter([[0,1],[0,2],[0,3],[0,4]]) == 2  # diameter between leaf nodes

# tree with two long branches
assert Solution().treeDiameter([[0,1],[0,2],[1,3],[1,4],[2,5],[5,6]]) == 5

Test	Why
[[0,1],[0,2]]	minimal tree with 3 nodes
[[0,1],[1,2],[2,3],[1,4],[4,5]]	moderate tree, diameter not through root
[]	single node edge case
linear chain	tests maximum path length in a line
star shape	tests multiple short branches, diameter between leaves
two long branches	checks longest path across separate branches

Edge Cases

1. Single-node tree: With no edges, the diameter is 0.