⚡Flashcard Drill➔
NeetCode #469LC-1245MediumTrees
← Back to All Problems

#469 · #1245 · Tree Diameter(树的直径)

📌 Problem Statement & Constraints

Given an undirected tree represented as a list of edges, return its diameter: the number of edges on the longest path between any two nodes. Constraints: 1 <= number of nodes <= 10^4, edges.length == number of nodes - 1.

💡 Core Algorithmic Approaches

  1. Root the tree arbitrarily (at node 0) and compute, for each node, the two largest depths among its children.
  2. The longest path through a node is the sum of those two depths.
  3. Track the maximum over all nodes.
  4. This is the same idea as the binary-tree diameter, adapted to an adjacency list with a parent guard.

💻 Benchmark Python3 Implementation

class Solution:
    def treeDiameter(self, edges: List[List[int]]) -> int:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)                 # undirected

        self.best = 0

        def dfs(node: int, parent: int) -> int:
            top1 = top2 = 0
            for c in g[node]:
                if c == parent:
                    continue               # do not go back up
                d = dfs(c, node)
                if d > top1:
                    top1, top2 = d, top1
                elif d > top2:
                    top2 = d
            self.best = max(self.best, top1 + top2)
            return top1 + 1

        if edges:
            dfs(0, -1)
        return self.best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node and edge is visited once.
💾 Space Complexity
O(n) for the adjacency list plus O(h) for the recursion.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the parent guard: the DFS would loop forever on an undirected graph.
  • Summing all child depths: only the two deepest matter.
  • Handling the single-node case: with no edges the diameter is 0, which the if edges guard returns.
  • Assuming the tree is a path: the two-deepest-children technique handles arbitrary branching.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems