The diameter of a tree is the number of edges in the longest path in that tree.
There is an undirected tree of n nodes labeled from 0 to n - 1. You are given a 2D array edges where edges.length == n - 1 and edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the tree.
Return the diameter of the tree.
Example 1:
Input: edges = [[0,1],[0,2]] Output: 2 Explanation: The longest path of the tree is the path 1 - 0 - 2.
Example 2:
Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]] Output: 4 Explanation: The longest path of the tree is the path 3 - 2 - 1 - 4 - 5.
Constraints:
n == edges.length + 11 <= n <= 1040 <= ai, bi < nai != biProblem Overview: You are given an undirected tree represented as a list of edges. The goal is to compute the tree’s diameter — the length of the longest path between any two nodes. The path does not need to pass through the root because the tree is unrooted.
Approach 1: DFS/BFS from Every Node (O(n^2) time, O(n) space)
Build an adjacency list for the tree, then run a traversal from every node. Each traversal (using DFS or BFS) computes the farthest distance reachable from that starting node. Track the maximum distance found across all traversals. Because a tree with n nodes has n-1 edges, each traversal costs O(n), and repeating it for all nodes results in O(n^2) time with O(n) space for the adjacency list and visited set. This method is straightforward but inefficient for large trees.
Approach 2: Two DFS Passes (O(n) time, O(n) space)
The key property of trees: if you start from any node and find the farthest node from it, that node must be one endpoint of the diameter. Run a first DFS from an arbitrary node (often node 0) to find the farthest node A. Then run a second DFS starting from A to find the farthest node B. The distance between A and B is the tree diameter. Each traversal processes every node and edge exactly once, giving O(n) time and O(n) space for the adjacency list and recursion stack. This technique works because trees have exactly one simple path between any two nodes.
Both traversals operate on a graph representation of the tree, so you first convert the edge list into an adjacency list. Either Depth-First Search or Breadth-First Search works for finding the farthest node. The underlying structure is still a tree, but treating it as an undirected graph simplifies traversal.
Recommended for interviews: The Two DFS Passes approach is the expected solution. Interviewers want to see that you recognize the diameter property and reduce the search from O(n^2) to O(n). Mentioning the brute force traversal first shows understanding of the problem space, then moving to the two-pass DFS demonstrates algorithmic optimization.
First, we arbitrarily select a node and start a depth-first search (DFS) from this node to find the farthest node from it, denoted as node a. Then, we start another DFS from node a to find the farthest node from node a, denoted as node b. It can be proven that the path between node a and node b is the diameter of the tree.
Time complexity is O(n), and space complexity is O(n), where n is the number of nodes.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS/BFS from Every Node | O(n^2) | O(n) | Useful for understanding the diameter definition or when constraints are very small |
| Two DFS Passes (Optimal) | O(n) | O(n) | Standard optimal solution for tree diameter problems in interviews and production code |
| Two BFS Passes | O(n) | O(n) | Alternative to DFS when recursion depth is a concern or iterative traversal is preferred |
Diameter Of Undirected Graph | Tree Diameter | Leetcode 1245 | Graph Concepts & Qns - 44 | MIK • codestorywithMIK • 11,332 views views
Watch 8 more video solutions →Practice Tree Diameter with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor