1245. Tree Diameter - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an undirected tree in the form of an edge list where each edge is represented as [u, v, w], meaning there is an edge between nodes u and v with a positive weight w. The diameter of the tree is defined as the length (i.e., the sum of edge weights) of the longest path between any two nodes in the tree. Your task is to compute and return this diameter.

Constraints:

The tree has n nodes (with node values typically ranging from 0 to n - 1).
The input edge list contains exactly n - 1 edges.
Each edge weight is a positive integer.
The tree is connected and acyclic.

Example 1:

Input: edges = [[0, 1, 3], [1, 2, 4], [2, 3, 5]]
Output: 12
Explanation: The longest path is from node 0 to node 3: 0 -> 1 -> 2 -> 3 with total weight 3 + 4 + 5 = 12.

Example 2:

Input: edges = [[0, 1, 1], [1, 2, 1], [1, 3, 1]]
Output: 2
Explanation: The longest path is between nodes 2 and 3 (through node 1): 2 -> 1 -> 3 with total weight 1 + 1 = 2.

Example 3:

Input: edges = [[1, 2, 2], [2, 3, 2], [2, 4, 1]]
Output: 4
Explanation: The longest path is from node 1 to node 3: 1 -> 2 -> 3 with total weight 2 + 2 = 4.

Hints

Hint 1: Start by picking any arbitrary node. Try to find the farthest node from it; this farthest node is guaranteed to be one end of the diameter.
Hint 2: Once you have the farthest node from the initial start, perform another traversal (using DFS or BFS) from that node to find the farthest node from it. The distance obtained in this second pass is the tree’s diameter.

Approach 1: Brute Force (Not Optimal)

Explanation:

Idea: For every pair of nodes, compute the path length (by DFS/BFS) and record the maximum distance.
How It Works:
1. For each node i, perform a DFS/BFS to calculate the distance to every other node.
2. Update the maximum distance found.
Complexity:
- Time: O(n²) – because for each of the n nodes, you may traverse most of the tree.
- Space: O(n) for the recursion stack or the queue.
Drawbacks:
- Although conceptually simple, this approach is inefficient for large trees (n could be in the thousands).

Approach 2: Two-Pass DFS/BFS (Optimal Approach)

Explanation:

Step 1: Choose an arbitrary node (say, node 0 or any node).
Step 2: Perform a DFS/BFS from the chosen node to find the farthest node from it (let’s call this node A).
Step 3: Now perform another DFS/BFS starting from node A to find the farthest node from A (call it node B).
Result: The distance from A to B is the diameter of the tree.

Why It Works:

Key Observation: In a tree, the farthest node from any arbitrary node is always an endpoint of the diameter. Thus, a second traversal from that endpoint will yield the maximum path length.

Complexity:

Time: O(n) – each DFS/BFS pass visits all nodes once.
Space: O(n) – for the recursion stack (DFS) or the queue (BFS), as well as the storage for the tree.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time Complexity:
Both DFS/BFS traversals visit every node exactly once. Therefore, the optimal approach runs in O(n) time.
Space Complexity:
O(n) space is needed for:
- The adjacency list representation of the tree.
- The recursion stack (in the worst case for a skewed tree) or the queue (if using BFS).

Step-by-Step Walkthrough & Visual Example

Walkthrough Example using Test Case 1:

Tree:

     0
      \
       1 (weight 3)
        \
         2 (weight 4)
          \
           3 (weight 5)

First DFS (starting from node 0):
- Start at node 0.
- From 0, go to node 1 (distance = 3).
- From 1, go to node 2 (distance = 3 + 4 = 7).
- From 2, go to node 3 (distance = 7 + 5 = 12).
- The farthest node found is node 3 with distance 12.
Second DFS (starting from node 3):
- Start at node 3.
- From 3, traverse back: node 2 (distance = 5), then node 1 (distance = 5 + 4 = 9), and finally node 0 (distance = 9 + 3 = 12).
- The farthest node from node 3 is node 0 with distance 12.
- Diameter = 12.

Common Mistakes, Edge Cases & Alternative Variations

Common Mistakes:

Missing Edge Case: Forgetting to handle a tree with only one node (diameter should be 0).
Wrong Data Structures: Using an inefficient data structure to represent the tree can lead to slower performance.
Infinite Recursion: Not properly checking the parent during DFS, which can lead to revisiting nodes.

Edge Cases:

Single Node Tree: Input with no edges. The diameter is 0.
Two Nodes: Only one edge exists; the diameter is the weight of that edge.

Alternative Variations:

Diameter of a Binary Tree: A similar problem where the tree is specifically a binary tree.
Longest Path in a Graph: Finding the longest path in more general graphs (usually much harder due to cycles).

Diameter of Binary Tree: Given a binary tree, find the length of the longest path between any two nodes.
Longest Path in a Directed Acyclic Graph (DAG): Given a DAG, find the longest path.
Minimum Height Trees: Find the roots of trees that give the minimum height when the tree is rooted.
Graph Traversal Problems: Problems involving DFS/BFS traversals in trees and graphs.
Network Delay Time: A problem that requires finding the longest time it takes for a signal to reach all nodes in a network.

1245. Tree Diameter - Detailed Explanation

Problem Statement

Hints

Approach 1: Brute Force (Not Optimal)

Explanation:

Approach 2: Two-Pass DFS/BFS (Optimal Approach)

Explanation:

Why It Works:

Complexity:

Python Code

Java Code

Complexity Analysis

Step-by-Step Walkthrough & Visual Example

Walkthrough Example using Test Case 1:

Common Mistakes, Edge Cases & Alternative Variations

Common Mistakes:

Edge Cases:

Alternative Variations:

Related Problems for Further Practice