8.6 Tree Diameter

The diameter of a tree is the length of the longest path between any two nodes.

algorithmstreesdata-structures

8.6 Tree Diameter

The diameter of a tree is the length of the longest path between any two nodes. Unlike height, which measures distance from a chosen root, diameter is a global property of the entire tree. It answers a different question:

What is the greatest distance that can exist between any pair of nodes?

Diameter appears in network design, distributed systems, phylogenetic trees, transportation networks, game maps, and many optimization problems. It is also a classic example of how local recursive information can be combined to compute a global result.

This recipe explores several approaches, beginning with a recursive solution and then introducing the widely used two-traversal technique.

Problem

You need to find the longest path in a tree.

Solution

A path may or may not pass through the root.

Consider this tree:

        0
      /   \\n     1     2
    /     / \\n   3     4   5
  /
 6

The longest path is:

6 → 3 → 1 → 0 → 2 → 5

The length is:

5 edges

One solution computes the diameter while calculating subtree heights.

package main

func diameter(tree [][]int, root int) int {
    best := 0

    var dfs func(int) int

    dfs = func(node int) int {
        tallest := 0
        secondTallest := 0

        for _, child := range tree[node] {
            h := dfs(child)

            if h > tallest {
                secondTallest = tallest
                tallest = h
            } else if h > secondTallest {
                secondTallest = h
            }
        }

        candidate := tallest + secondTallest

        if candidate > best {
            best = candidate
        }

        return tallest + 1
    }

    dfs(root)

    return best
}

The function returns the diameter measured in edges.

Discussion

The key observation is that every diameter belongs to one of two categories:

  • It lies entirely inside a child subtree.
  • It passes through the current node.

The first case is handled recursively.

The second case requires only the two tallest child branches.

Consider:

        X
      / | \\n     A  B  C

Suppose:

height(A) = 7
height(B) = 5
height(C) = 3

The longest path through X uses the two largest heights:

7 + 5 = 12

The branch of height 3 cannot improve the answer.

This leads directly to the recursive algorithm. Each node tracks its two largest child heights and updates the global diameter candidate.

Understanding the Recurrence

Height answers:

How far can I go downward?

Diameter answers:

How far can I go in two directions?

At every node:

diameter candidate =
largest child height +
second largest child height

For a leaf:

height = 1
diameter contribution = 0

As recursion returns upward, larger candidates emerge.

This pattern appears frequently in tree dynamic programming: a node combines the best results from multiple children to construct a larger solution.

Diameter Using Two DFS Traversals

A more famous approach uses two traversals.

The algorithm is surprisingly simple:

  1. Start from any node.
  2. Find the farthest node A.
  3. Start from A.
  4. Find the farthest node B.
  5. The distance from A to B is the diameter.

For example:

0
├── 1
│   └── 3
│       └── 6
└── 2
    ├── 4
    └── 5

Starting from node 0:

Farthest node = 6

Starting from node 6:

Farthest node = 5

The path:

6 → 3 → 1 → 0 → 2 → 5

is the diameter.

Implementation:

func farthest(
    adj [][]int,
    start int,
) (int, int) {
    bestNode := start
    bestDist := 0

    var dfs func(int, int, int)

    dfs = func(node, parent, dist int) {
        if dist > bestDist {
            bestDist = dist
            bestNode = node
        }

        for _, next := range adj[node] {
            if next == parent {
                continue
            }

            dfs(next, node, dist+1)
        }
    }

    dfs(start, -1, 0)

    return bestNode, bestDist
}

Diameter computation becomes:

func treeDiameter(adj [][]int) int {
    a, _ := farthest(adj, 0)
    _, diameter := farthest(adj, a)

    return diameter
}

This technique is often easier to remember than the height-based approach.

Recovering the Diameter Path

Sometimes the path itself is required.

Store parent pointers during the second traversal.

parent := make([]int, len(adj))

When exploring:

parent[next] = node

After finding the farthest node, walk backward through the parent array.

path := []int{}

for current := target; current != -1; current = parent[current] {
    path = append(path, current)
}

Reverse the result to obtain the diameter path.

This approach is useful in routing systems, dependency analysis, and visualization tools where the actual path matters more than its length.

Diameter of a Binary Tree

Binary-tree interview problems often use a node structure:

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

The recursive solution adapts naturally.

func diameterBinary(root *Node) int {
    best := 0

    var height func(*Node) int

    height = func(node *Node) int {
        if node == nil {
            return 0
        }

        left := height(node.Left)
        right := height(node.Right)

        if left+right > best {
            best = left + right
        }

        if left > right {
            return left + 1
        }

        return right + 1
    }

    height(root)

    return best
}

The algorithm computes height and diameter simultaneously.

Each node contributes:

left height + right height

as a candidate diameter.

Diameter and Tree Centers

Diameter leads naturally to the concept of a tree center.

Consider a diameter path:

A → ... → B

The center lies near the middle.

If the diameter length is even:

one center node

If the diameter length is odd:

two center nodes

Tree centers are useful because they minimize the maximum distance to all other nodes.

Applications include:

  • Server placement
  • Network hubs
  • Distribution centers
  • Broadcast trees

Many optimization problems begin by finding the diameter and then identifying its midpoint.

Complexity Analysis

Let:

  • n = number of nodes

For the height-based solution:

Operation Complexity
DFS traversal O(n)
Height computation O(n)
Diameter computation O(n)
Extra space O(h)

For the two-traversal method:

Operation Complexity
First traversal O(n)
Second traversal O(n)
Total O(n)
Extra space O(h)

Both methods are linear.

The choice usually depends on what other information the algorithm already computes.

Common Mistakes

A common mistake is confusing diameter with height.

Height measures distance from a node downward.

Diameter measures distance between any two nodes.

Consider:

0
|
1
|
2
|
3

Height from the root:

3

Diameter:

3

They happen to be equal.

But in a more complex tree:

    0
   / \\n  1   2
 /     \\n3       4

Height:

2

Diameter:

4

The values are different.

Another mistake is keeping only the largest child height when computing diameter recursively. The longest path through a node requires the two largest child heights.

A third mistake is forgetting that diameter may not pass through the chosen root. Many incorrect implementations assume otherwise and miss longer paths contained in deeper subtrees.

Takeaway

Tree diameter is the longest path between any two nodes. The recursive solution combines subtree heights, while the two-traversal method finds opposite endpoints of the longest path. Both run in linear time and illustrate a recurring theme in tree algorithms: local information, when aggregated correctly, reveals global structure. Diameter also serves as a foundation for tree centers, rerooting techniques, and many advanced optimization problems.