Diameter of Binary Tree

Given the root of a binary tree, return its diameter: the number of edges on the longest path between any two nodes in the tree. A path moves along parent-child links, never visits a node twice, and does not have to pass through the root.

A tree with a single node has diameter 0.

Trees are given in level order with null marking a missing child, so [5,3,8,1,4,null,9] is a root 5 with children 3 and 8, where 3 has children 1 and 4 and 8 has a right child 9.

Example 1

Example 2

Example 3

Constraints

• The number of nodes is between 1 and 104.
• The depth of the tree is at most 500.
• -100 <= Node.val <= 100

Pattern Path · Trees: DFS · problem 82 of 169

Start simple

For every node, compute the heights of both subtrees from scratch and take the best sum: O(n²) time on a chain-like tree.

The key idea

Look at any path and find its highest node, the point where it stops going up and starts going down. Call it the path's peak. From the peak the path descends into the left subtree and into the right subtree. To make the path as long as possible for that peak, each side should go as deep as it can, so the best path peaking at x has length height(x.left) + height(x.right), where height counts nodes on the deepest downward path (0 for an empty subtree).

The diameter is the maximum of that quantity over all nodes. A single post-order DFS gives both numbers at once: the recursive call returns the height of a subtree, and before returning, each node updates a shared best with left + right. Each node is visited once, so the whole computation is linear.

The key trick is that the function returns one thing (height, which the parent needs) while recording another (the diameter candidate, which only the global answer needs).

Complexity

• Time: O(n)
• Space: O(h) for the recursion, where h is the tree height

Python

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        best = 0

        def height(node):
            """Number of nodes on the deepest downward path from node."""
            nonlocal best
            if node is None:
                return 0
            left = height(node.left)
            right = height(node.right)
            best = max(best, left + right)   # longest path that peaks at node
            return 1 + max(left, right)

        height(root)
        return best

JavaScript

var diameterOfBinaryTree = function(root) {
  let best = 0;

  // Number of nodes on the deepest downward path from node.
  const height = (node) => {
    if (node === null) return 0;
    const left = height(node.left);
    const right = height(node.right);
    best = Math.max(best, left + right);  // longest path that peaks at node
    return 1 + Math.max(left, right);
  };

  height(root);
  return best;
};

What the interviewer is checking

It tests whether you can make a recursive function return one value while tracking a different global answer, and whether you realise the best path need not go through the root.

Mistakes to avoid

• Only checking the path through the root; the longest path can sit entirely inside one subtree.
• Mixing up edges and nodes, giving an answer that is off by one.
• Recomputing subtree heights for every node, which turns the solution quadratic.

Follow-ups to expect

• Return the nodes on the longest path, not just its length. (Track the best peak and walk down.)
• Diameter of a general tree with many children. (Combine the two tallest children.)
• Maximum path sum with node weights. (Same peak idea, clamp negative branches.)

In real software

Finding the two most distant points in a hierarchy, such as the worst-case hop count in a tree-shaped network or the longest dependency chain through a shared ancestor, is a tree-diameter computation.

Practice next