Tree Diameter solution and explanation
Google
8 more videos on this problem
Diameter Of Undirected Graph | Tree Diameter | Leetcode 1245 | Graph Concepts & Qns - 44 | MIKcodestorywithMIK · 36:19 · 13K views
Leetcode 1245: Tree DiameterAlgorithms Casts · 30:17 · 2K views
LeetCode 1245. Tree Diameter | JSer - JavaScript & AlgorithmJSer · 17:43 · 864 views
1245. Tree Diameter | Input is in the form of an Array of edges | Leetcode Premium Prob, Simple DFSAnmol Gera · 5:49 · 823 views
1245. Tree Diameter - Week 4/5 Leetcode February ChallengeProgramming Live with Larry · 9:10 · 703 views
Leetcode 1245. Tree Diameter (Tree Diameter)LetsCode · 15:09 · 570 views
Leetcode 1245. Tree Diameter (topological sort)LetsCode · 14:04 · 256 views
LeetCode Medium: 1245. Tree Diameterrobzingcod · 10:24 · 53 views
LeetCode 1245: Tree DiameterAlitaCode · 28:50 · 6 views
The problem
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 != bi
Approach overview
Problem 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.
Solution
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:
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
def dfs(i: int, fa: int, t: int):
for j in g[i]:
if j != fa:
dfs(j, i, t + 1)
nonlocal ans, a
if ans < t:
ans = t
a = i
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
ans = a = 0
dfs(0, -1, 0)
dfs(a, -1, 0)
return ansclass Solution {
private List<Integer>[] g;
private int ans;
private int a;
public int treeDiameter(int[][] edges) {
int n = edges.length + 1;
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (var e : edges) {
int a = e[0], b = e[1];
g[a].add(b);
g[b].add(a);
}
dfs(0, -1, 0);
dfs(a, -1, 0);
return ans;
}
private void dfs(int i, int fa, int t) {
for (int j : g[i]) {
if (j != fa) {
dfs(j, i, t + 1);
}
}
if (ans < t) {
ans = t;
a = i;
}
}
}class Solution {
public:
int treeDiameter(vector<vector<int>>& edges) {
int n = edges.size() + 1;
vector<int> g[n];
for (auto& e : edges) {
int a = e[0], b = e[1];
g[a].push_back(b);
g[b].push_back(a);
}
int ans = 0, a = 0;
auto dfs = [&](this auto&& dfs, int i, int fa, int t) -> void {
for (int j : g[i]) {
if (j != fa) {
dfs(j, i, t + 1);
}
}
if (ans < t) {
ans = t;
a = i;
}
};
dfs(0, -1, 0);
dfs(a, -1, 0);
return ans;
}
};function treeDiameter(edges: number[][]): number {
const n = edges.length + 1;
const g: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
let [ans, a] = [0, 0];
const dfs = (i: number, fa: number, t: number): void => {
for (const j of g[i]) {
if (j !== fa) {
dfs(j, i, t + 1);
}
}
if (ans < t) {
ans = t;
a = i;
}
};
dfs(0, -1, 0);
dfs(a, -1, 0);
return ans;
}func treeDiameter(edges [][]int) (ans int) {
n := len(edges) + 1
g := make([][]int, n)
for _, e := range edges {
a, b := e[0], e[1]
g[a] = append(g[a], b)
g[b] = append(g[b], a)
}
a := 0
var dfs func(i, fa, t int)
dfs = func(i, fa, t int) {
for _, j := range g[i] {
if j != fa {
dfs(j, i, t+1)
}
}
if ans < t {
ans = t
a = i
}
}
dfs(0, -1, 0)
dfs(a, -1, 0)
return
}Complexity analysis
| 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 |
Frequently asked questions
Is Tree Diameter easy or hard?
Tree Diameter is generally considered a medium-level problem. The implementation of DFS is simple, but recognizing the two-pass traversal property of trees requires some graph algorithm intuition.
Tree Diameter Python/Java solution
Most implementations build an adjacency list using a dictionary or list of lists, then run two DFS traversals. The same logic works across Python, Java, C++, Go, and TypeScript with only minor syntax differences.
How to solve Tree Diameter in O(n)?
Convert the edge list into an adjacency list. Perform a DFS from any node to locate the farthest node A. Then perform a second DFS starting from A to find the farthest node B and measure the distance. That distance equals the tree diameter.
What is the best approach for Tree Diameter?
The most efficient method is the Two DFS Passes technique. Run a DFS from any node to find the farthest node A, then run another DFS from A to find the farthest node B. The distance between A and B is the diameter. This approach runs in O(n) time and O(n) space.
Is Tree Diameter asked at Google/Amazon/Meta?
Tree diameter is a common graph and tree interview problem and variations appear at companies like Google, Amazon, Meta, and Microsoft. It tests graph traversal skills, adjacency list construction, and understanding of tree properties.
What data structure is used in Tree Diameter?
The tree is typically stored as an adjacency list because the input is given as edges. Traversal uses either Depth-First Search (DFS) with recursion or Breadth-First Search (BFS) with a queue to compute distances between nodes.
What is the time complexity of Tree Diameter?
The optimal algorithm runs in O(n) time where n is the number of nodes in the tree. Each DFS or BFS traversal visits every node and edge once, and the algorithm performs exactly two traversals.