Graph Theory37 sections · 1633 units
Open in Course

Common Mistakes

What to avoid

Mistake 11: Running BFS from every node to find diameter. That is O(n2)O(n^2). Use two-BFS instead. Mistake 22: Thinking diameter always passes through the root. It does not. The longest path can be anywhere in the tree. Mistake 33: Forgetting to handle both diameter endpoints in Tree Distances I.

You need the max of distances to both endpoints. Mistake 44: Trying to solve Tree Distances II with BFS from each node. That times out. Use rerooting DP.