Diameter of a Tree

March 2026 · 7 min read

The Problem

The diameter (also called the width) of a tree is the number of edges on the longest path between any two nodes. This path may or may not pass through the root.

A common mistake is assuming the diameter always goes through the root. In a left-skewed tree, the longest path might be entirely within the left subtree.

The Key Insight

For every node, consider the longest path that passes through that node. This path goes from the deepest leaf in its left subtree, up through the node, and down to the deepest leaf in its right subtree. The length of this path is:

The diameter is the maximum of this value across all nodes in the tree. The brilliant part: we can compute this during the same DFS we use for height computation, no extra pass needed.

Algorithm Walkthrough

We do a single post-order DFS. At each node:

1. Recursively compute the depth of the left subtree (L).
2. Recursively compute the depth of the right subtree (R).
3. The longest path through this node is L + R edges. Update the global maximum if this is the best so far.
4. Return 1 + max(L, R) upward (so the parent can use our depth).

Notice this is the same bottom-up pattern as height computation, with one addition: we track a running maximum along the way.

The Code

int diameter(TreeNode* root) {
    int result = 0;
    std::function<int(TreeNode*)> depth = [&](TreeNode* node) -> int {
        if (!node) return 0;
        int L = depth(node->left);   // depth of left subtree
        int R = depth(node->right);  // depth of right subtree
        result = std::max(result, L + R);  // update diameter candidate
        return 1 + std::max(L, R);   // return my depth to parent
    };
    depth(root);
    return result;  // longest path found anywhere in the tree
}

Time: O(n), single DFS, every node visited once.
Space: O(h) for the recursion stack.

Why Not Just root.leftHeight + root.rightHeight?

Because the longest path might not pass through the root at all. Consider:

        1
       /
      2
     / \
    3   4
   /
  5

The diameter is 3 (path: 5→3→2→4), passing through node 2, not the root. The root only has left height 3 and right height 0, giving a path of 3 through the root. In this case they happen to be equal, but in general the diameter can be entirely below the root.

Related Problems

• Maximum Path Sum: Same structure as diameter, but instead of counting edges, sum node values along the path. Track leftMax + rightMax + node->val as candidate. Return max(leftMax, rightMax) + node->val upward (or 0 if negative, you can abandon a subtree).
• Longest Path with Same Value: Diameter variant where you only extend through children with the same value as the current node.
• Binary Tree Cameras: Another post-order problem where each node returns status upward.