Tree Diameter and Path Problems

The diameter of a tree is the length of the longest path between any two nodes. This path may or may not pass through the root — a critical insight that trips up many people. Diameter problems are a gateway to a whole family of “path” problems in trees.

What is tree diameter?

The diameter (also called the width) of a tree is the number of edges on the longest path between any two nodes. Some definitions count nodes instead of edges — the difference is always 1.

        1
       / \
      2   3
     / \
    4   5
   /     \
  8       9

Diameter = 4 (path: 8 → 4 → 2 → 5 → 9)
Note: This path does NOT go through the root!

Single-DFS approach (binary tree)

The key insight: for any node, the longest path through that node is left_depth + right_depth. The diameter is the maximum of this value across all nodes.

def diameter_of_binary_tree(root):
    """Return the diameter (number of edges) of a binary tree."""
    max_diameter = [0]

    def depth(node):
        if node is None:
            return 0

        left_d = depth(node.left)
        right_d = depth(node.right)

        # The longest path through this node
        max_diameter[0] = max(max_diameter[0], left_d + right_d)

        # Return depth for parent's calculation
        return 1 + max(left_d, right_d)

    depth(root)
    return max_diameter[0]

Time: O(n) — visit each node once. Space: O(h) — recursion stack depth.

Why this works

At every node, we compute two things:

1. Depth: the longest path going downward from this node (returned to parent)
2. Path through this node: left_depth + right_depth (checked against global max)

The diameter must pass through some node as its highest point. By checking every node, we find it.

Walkthrough

        1
       / \
      2   3
     / \
    4   5
   /
  8

depth(8): left=0, right=0, path=0, return 1
depth(4): left=1(from 8), right=0, path=1, return 2
depth(5): left=0, right=0, path=0, return 1
depth(2): left=2(from 4), right=1(from 5), path=3 ← max!, return 3
depth(3): left=0, right=0, path=0, return 1
depth(1): left=3(from 2), right=1(from 3), path=4 ← new max!, return 4

Diameter = 4 (path: 8-4-2-1-3... wait, but 8-4-2-5 is only 3)
Actually: at node 1, left_d=3, right_d=1, path=4
Path: 8 → 4 → 2 → 1 → 3 (4 edges)

Common mistake

Do NOT just compute depth(root.left) + depth(root.right). The longest path might be entirely within one subtree:

    1
   /
  2
 / \
3   4
     \
      5

Diameter = 3 (path: 3 → 2 → 4 → 5)
But depth(root.left) + depth(root.right) = 3 + 0 = 3
This happens to work here, but only by coincidence.
The check must happen at EVERY node.

Diameter with node count

If you want the number of nodes on the diameter path instead of edges:

def diameter_nodes(root):
    """Return number of nodes on the longest path."""
    max_nodes = [0]

    def depth(node):
        if node is None:
            return 0
        left_d = depth(node.left)
        right_d = depth(node.right)
        # +1 for the current node
        max_nodes[0] = max(max_nodes[0], left_d + right_d + 1)
        return 1 + max(left_d, right_d)

    depth(root)
    return max_nodes[0]

Two-BFS approach (for general/N-ary trees)

For unrooted trees (graphs that are trees), the two-BFS approach is elegant:

1. Pick any node, BFS to find the farthest node from it (call it u)
2. BFS from u to find the farthest node from u (call it v)
3. The distance from u to v is the diameter

from collections import deque

def tree_diameter_bfs(adj, n):
    """Find diameter of an unrooted tree using two BFS.
    adj: adjacency list, n: number of nodes.
    """
    def bfs_farthest(start):
        """BFS from start, return (farthest_node, distance)."""
        dist = [-1] * n
        dist[start] = 0
        queue = deque([start])
        farthest = start

        while queue:
            node = queue.popleft()
            for neighbor in adj[node]:
                if dist[neighbor] == -1:
                    dist[neighbor] = dist[node] + 1
                    queue.append(neighbor)
                    if dist[neighbor] > dist[farthest]:
                        farthest = neighbor

        return farthest, dist[farthest]

    # BFS 1: find one endpoint of diameter
    u, _ = bfs_farthest(0)
    # BFS 2: find the other endpoint and the diameter
    v, diameter = bfs_farthest(u)

    return diameter

Why two-BFS works

Claim: The farthest node from any node in a tree is always an endpoint of some diameter path.

Proof sketch: If the farthest node u from an arbitrary start were not a diameter endpoint, there would exist a longer path in the tree, contradicting u being farthest.

Example

# Tree (adjacency list):
# 0 -- 1 -- 2 -- 3 -- 4
#      |
#      5 -- 6

adj = [
    [1],        # 0
    [0, 2, 5],  # 1
    [1, 3],     # 2
    [2, 4],     # 3
    [3],        # 4
    [1, 6],     # 5
    [5],        # 6
]

print(tree_diameter_bfs(adj, 7))
# BFS from 0: farthest is 4 (distance 4)
# BFS from 4: farthest is 6 (distance 5)
# Diameter = 5 (path: 6-5-1-2-3-4)

Maximum path sum

A harder variant: find the path with the maximum sum of node values. The path can start and end at any node.

def max_path_sum(root):
    """Find maximum path sum in a binary tree (LeetCode 124)."""
    max_sum = [float('-inf')]

    def max_gain(node):
        if node is None:
            return 0

        # Maximum gain from left and right (ignore negative paths)
        left_gain = max(max_gain(node.left), 0)
        right_gain = max(max_gain(node.right), 0)

        # Path through this node
        path_sum = node.val + left_gain + right_gain
        max_sum[0] = max(max_sum[0], path_sum)

        # Return max gain for parent (can only go one direction)
        return node.val + max(left_gain, right_gain)

    max_gain(root)
    return max_sum[0]

Key difference from diameter: we use max(gain, 0) to ignore negative subtrees. A path can choose to NOT extend into a subtree if it would decrease the sum.

Walkthrough

       -10
       /  \
      9   20
         /  \
        15   7

max_gain(9):  left=0, right=0, path=9, return 9
max_gain(15): left=0, right=0, path=15, return 15
max_gain(7):  left=0, right=0, path=7, return 7
max_gain(20): left=15, right=7, path=20+15+7=42 ← max!, return 20+15=35
max_gain(-10): left=max(9,0)=9, right=max(35,0)=35
              path=-10+9+35=34, return -10+35=25

Maximum path sum = 42 (path: 15 → 20 → 7)

Longest path in a weighted tree

When edges have weights, the diameter is the path with maximum total weight:

def weighted_diameter(adj, n):
    """Find diameter of weighted tree.
    adj[u] = [(v, weight), ...]
    """
    def bfs_farthest(start):
        dist = [-1] * n
        dist[start] = 0
        queue = deque([start])
        farthest = start

        while queue:
            node = queue.popleft()
            for neighbor, weight in adj[node]:
                if dist[neighbor] == -1:
                    dist[neighbor] = dist[node] + weight
                    queue.append(neighbor)
                    if dist[neighbor] > dist[farthest]:
                        farthest = neighbor

        return farthest, dist[farthest]

    u, _ = bfs_farthest(0)
    v, diameter = bfs_farthest(u)
    return diameter

Finding the actual diameter path

Sometimes you need the path itself, not just its length:

def diameter_path(root):
    """Return the actual nodes on the diameter path."""
    max_info = [0, []]  # [max_diameter, path]

    def depth_with_path(node):
        if node is None:
            return 0, []

        left_d, left_path = depth_with_path(node.left)
        right_d, right_path = depth_with_path(node.right)

        current_diameter = left_d + right_d
        if current_diameter > max_info[0]:
            max_info[0] = current_diameter
            # Reverse left path + current + right path
            max_info[1] = left_path[::-1] + [node.val] + right_path

        if left_d >= right_d:
            return left_d + 1, left_path + [node.val]
        else:
            return right_d + 1, right_path + [node.val]

    depth_with_path(root)
    return max_info[1]

Relation to depth problems

Many tree problems are disguised diameter or depth problems:

Problem	Technique
Maximum depth	DFS returning depth
Diameter	DFS tracking left+right depth at each node
Maximum path sum	Same as diameter but with sums
Longest path with same values	Diameter but only count matching values
Farthest node from leaves	BFS from all leaves simultaneously

The pattern is always the same: at each node, combine information from left and right subtrees.

Longest univalue path

A variation where the path must have all the same values:

def longest_univalue_path(root):
    """Find longest path where all nodes have the same value."""
    max_length = [0]

    def dfs(node):
        if node is None:
            return 0

        left = dfs(node.left)
        right = dfs(node.right)

        # Extend left path only if values match
        left_path = left + 1 if node.left and node.left.val == node.val else 0
        right_path = right + 1 if node.right and node.right.val == node.val else 0

        max_length[0] = max(max_length[0], left_path + right_path)

        return max(left_path, right_path)

    dfs(root)
    return max_length[0]

Sum of distances in tree

A harder problem (LeetCode 834): find the sum of distances from each node to all other nodes.

def sum_of_distances(n, edges):
    """For each node, compute sum of distances to all other nodes."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    count = [1] * n  # subtree sizes
    result = [0] * n

    # Post-order: compute subtree sizes and result[0]
    def dfs1(node, parent):
        for child in adj[node]:
            if child != parent:
                dfs1(child, node)
                count[node] += count[child]
                result[node] += result[child] + count[child]

    # Pre-order: compute result for all nodes from result[0]
    def dfs2(node, parent):
        for child in adj[node]:
            if child != parent:
                # Moving from node to child:
                # count[child] nodes get 1 closer
                # (n - count[child]) nodes get 1 farther
                result[child] = result[node] - count[child] + (n - count[child])
                dfs2(child, node)

    dfs1(0, -1)
    dfs2(0, -1)
    return result

This uses a rerooting technique — compute the answer for one node, then efficiently derive answers for all other nodes.

Practice problems

1. Diameter of Binary Tree (LeetCode 543) — The classic, single DFS
2. Binary Tree Maximum Path Sum (LeetCode 124) — Diameter variant with sums
3. Longest Univalue Path (LeetCode 687) — Constrained diameter
4. Sum of Distances in Tree (LeetCode 834) — Rerooting technique
5. Tree Diameter (LeetCode 1245) — Two-BFS on general tree
6. Longest Path With Different Adjacent Characters (LeetCode 2246)
7. Maximum Difference Between Node and Ancestor (LeetCode 1026)
8. Path Sum III (LeetCode 437) — Count paths with target sum

Key takeaways

• The diameter may NOT pass through the root — check at every node
• Single-DFS: at each node, the longest path through it is left_depth + right_depth
• Two-BFS works for unrooted/general trees and is simpler to implement
• Maximum path sum is a diameter variant with max(gain, 0) to skip negative branches
• Many tree problems reduce to “combine left and right subtree info at each node”
• The rerooting technique extends per-subtree answers to the entire tree