What Is Graph Diameter? The Longest Shortest Path Explained

You read "longest shortest path" and immediately suspect a typo. It isn't. The diameter of a graph is the longest shortest path between any two nodes. It sounds like a riddle a CS professor tells to watch freshmen suffer, but the concept clicks fast once you stop fighting the phrasing.

"Longest Shortest"? That's Not a Typo

The phrase trips people up, so read it slowly.

The "shortest path" between two nodes is the minimum number of edges you'd travel to get from one to the other. Think driving distance between cities, not crow-flies. For weighted graphs you sum edge weights; for unweighted graphs you count edges.

"Longest" over all those shortest distances means: find the pair of nodes that are farthest apart, even by their best possible route.

If you can get from A to B in 3 hops and from C to D only in 7 hops, the diameter is at least 7. You're asking: across the whole graph, which two nodes are most isolated from each other? The diameter measures the graph's "width" in the same intuitive sense that the diameter of a circle measures how wide it is. Two different concepts sharing the same word was a deliberate choice by someone who wanted graph theory to feel like a personality test.

The Hub vs. the Chain

Take this five-node path graph:

1 -- 2 -- 3 -- 4 -- 5

Shortest path from node 1 to node 5 is 4 edges. No pair gets farther apart. Diameter = 4.

Now consider a star: one center node connected to four leaves.

The farthest any two nodes can be is two hops (any leaf to any other leaf, through the center). Diameter = 2. The hub collapses everything.

Dense, hub-connected graphs have small diameters. Long chains have large ones. Social networks famously have diameters around 6. That's where "six degrees of separation" comes from: you can reach any person on Earth through at most six acquaintance links. A linked list of a million nodes has a diameter of 999,999. Same asymptotic size, wildly different structure. Your social graph is not a linked list, thankfully.

A disconnected graph is a special case. If some pair of nodes has no path between them, their distance is infinite, and the diameter is technically infinite too. In practice you compute per connected component, or the problem guarantees connectivity. LeetCode diameter problems always give you a connected input. Clarify the assumption, move on, don't spend five minutes agonizing over it in an interview.

Computing Diameter on a Tree: The Two-BFS Trick

For trees there's an elegant O(V) algorithm. Most candidates don't know it exists, reach for "BFS from every node," and produce O(V²) on a structure that didn't ask for it.

The trick:

Pick any node. Call it s.
Run BFS from s. Find the farthest node. Call it u.
Run BFS from u. Find the farthest node from u. Call it v.
The distance from u to v is the diameter.

Two passes. Done.

The key insight: the farthest node from any starting point in a tree is always one endpoint of a diameter path. Proof by contradiction: suppose it weren't, and some other path (a, b) were longer. You can show that (u, v) found in the second pass must be at least as long as (a, b). The argument works because trees have exactly one path between any two nodes, which lets you reason about path extensions without worrying about cycles. Cycles would break everything here, and they will, which is why this trick is tree-only.

from collections import deque

def tree_diameter(edges: list[tuple[int, int]], n: int) -> int:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    def bfs(start: int) -> tuple[int, int]:
        dist = [-1] * n
        dist[start] = 0
        q = deque([start])
        farthest, max_dist = start, 0
        while q:
            node = q.popleft()
            for nei in adj[node]:
                if dist[nei] == -1:
                    dist[nei] = dist[node] + 1
                    q.append(nei)
                    if dist[nei] > max_dist:
                        farthest, max_dist = nei, dist[nei]
        return farthest, max_dist

    u, _ = bfs(0)
    _, diameter = bfs(u)
    return diameter

Time: O(V). Space: O(V). Two passes, linear, done.

Binary Trees: The DFS Post-Order Pattern

LeetCode 543, "Diameter of Binary Tree," shows up at nearly every major tech company. The two-BFS approach works, but there's a cleaner DFS formulation that matches the recursive structure of the tree.

At every node, the longest path passing through that node equals depth(left subtree) + depth(right subtree). Track the maximum as you recurse post-order.

def diameterOfBinaryTree(root) -> int:
    result = 0

    def depth(node) -> int:
        nonlocal result
        if not node:
            return 0
        left = depth(node.left)
        right = depth(node.right)
        result = max(result, left + right)
        return 1 + max(left, right)

    depth(root)
    return result

The diameter path doesn't have to pass through the root, and that's the subtle point this pattern handles. By computing depth post-order at every node, you evaluate every candidate path in one pass.

The classic bug here is returning diameter instead of depth from the helper. The helper must return depth so the recursion computes correctly. The diameter lives as a side effect tracked in result. This distinction has ended more interviews than it should have. If you take nothing else from this section, take the mantra: helper returns depth, diameter is a side effect.

General Graphs: The Expensive Version

The two-BFS trick only works for trees. General graphs have cycles, which breaks the reasoning that made the trick valid.

For a general unweighted graph, you run BFS from every node and track the maximum distance found. There's no shortcut. You earned that O(V(V + E)).

from collections import deque

def graph_diameter(adj: list[list[int]], n: int) -> int:
    def bfs_max_dist(start: int) -> int:
        dist = [-1] * n
        dist[start] = 0
        q = deque([start])
        max_dist = 0
        while q:
            node = q.popleft()
            for nei in adj[node]:
                if dist[nei] == -1:
                    dist[nei] = dist[node] + 1
                    q.append(nei)
                    max_dist = max(max_dist, dist[nei])
        return max_dist

    return max(bfs_max_dist(i) for i in range(n))

Time: O(V(V + E)). Space: O(V).

For weighted graphs, swap BFS for Dijkstra per node: O(V(V + E) log V). For dense graphs where you want all-pairs shortest paths at once, Floyd-Warshall runs in O(V³) with O(V²) space and you scan the resulting distance matrix for the maximum. It's the sledgehammer approach. Sometimes the sledgehammer is right.

Graph type	Algorithm	Time	Space
Unweighted tree	Two BFS	O(V)	O(V)
Binary tree	DFS post-order	O(V)	O(h)
Unweighted general graph	BFS from every node	O(V(V+E))	O(V)
Weighted graph (sparse)	Dijkstra from every node	O(V(V+E) log V)	O(V)
Dense graph (all pairs)	Floyd-Warshall	O(V³)	O(V²)

The O(h) space for binary tree DFS is the call stack depth. For a balanced tree that's O(log V). For a degenerate chain it's O(V), same as two-BFS. The universe has a sense of humor.

Why Graph Diameter Shows Up in Coding Interviews

Diameter problems appear in two direct forms and several disguised ones.

Direct form 1: Binary tree diameter. LeetCode 543 appears at nearly every major tech company. The difficulty is not the algorithm, it's the implementation trap of returning the wrong thing from the helper. Knowing the depth-as-return-value, diameter-as-side-effect pattern cold is worth memorizing.

Direct form 2: Tree from edge list. LeetCode 1245 gives you a tree as an edge list and asks for its diameter. The two-BFS approach handles it in O(V). Candidates who don't know the trick reach for "BFS from every node" and get O(V²) on a tree, which works but signals weaker graph intuition. It's the kind of thing an interviewer writes down.

Disguised forms. The concept surfaces any time an interviewer asks about farthest nodes, critical network paths, or broadcast time. "What's the minimum time to send a message to every node if messages travel one hop per second?" That's diameter of the spanning tree. "What's the longest path in this DAG?" That's a variant using topological sort and dynamic programming, but the underlying question is the same shape.

Diameter also connects directly to BFS vs DFS tradeoffs. For trees, BFS naturally finds shortest paths and gives the cleaner mental model for the two-pass argument. For binary trees, DFS post-order matches the recursive structure and avoids converting to an adjacency list.

If you want to practice explaining the two-BFS insight out loud and get structured feedback on whether your reasoning is landing, SpaceComplexity runs voice-based mock interviews that test exactly this kind of structural thinking, not just whether your code compiles.

Common Mistakes Worth Naming

Confusing diameter with depth. Depth is the longest path from root to leaf. Diameter is the longest path between any two nodes. In a lopsided tree where all nodes hang left, the depth can be large while the diameter runs through the "widest" part, which might not involve the deepest leaf. These two numbers are completely different. They just both involve the word "longest," which is how confusion gets invited in.

Using O(V²) on a tree. Running BFS from every node is correct but wasteful by a factor of V. The two-BFS trick gives O(V). In an interview, starting with the wasteful approach is fine. Knowing how to improve it to the linear solution is what gets you hired.

Off-by-one on edges vs. nodes. Diameter is measured in edges, not nodes. The path 1-2-3 has diameter 2 (two edges), not 3 (three nodes). LeetCode 543 uses the edge definition, which is standard. Clarify the unit before coding. This is the kind of off-by-one that doesn't show up until you're running your last test case with 30 seconds left.

Forgetting non-root paths in binary trees. The widest path might run entirely within one subtree, through a non-root node. A naive "depth of left plus depth of right at the root" misses this. The post-order DFS that updates result at every node catches it. Check this edge case explicitly in your dry run. It's the first thing an interviewer looks for after you say you're done.