MediumNo. 1245LeetCode Premium
Tree Diameter — LeetCode 1245 Python Solution
- Pattern
- Topological Sort
- Topics
- Tree, Depth-First Search, Breadth-First Search, Graph, Topological Sort
- Reading time
- 3 min
- Source
- leetcode.com
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.
Example
- Input
- edges = [[0,1],[0,2]]
- Output
- 2
- Explanation
- The longest path of the tree is the path 1 - 0 - 2.
Python solution
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 ansComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Topological Sort
Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1245. Tree Diameter is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.
The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0802 | Find Eventual Safe States | Medium |
| 1203 | Sort Items by Groups Respecting Dependencies | Hard |
| 1361 | Validate Binary Tree Nodes | Medium |
Frequently asked questions
- How hard is LeetCode 1245. Tree Diameter?
LeetCode 1245. Tree Diameter is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1245. Tree Diameter?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1245. Tree Diameter?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1245. Tree Diameter cover?
LeetCode 1245. Tree Diameter is tagged Tree, Depth-First Search, Breadth-First Search, Graph and Topological Sort on LeetCode.
- Is LeetCode 1245. Tree Diameter a premium problem?
Yes. LeetCode 1245. Tree Diameter is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.