Diameter of a binary tree

The longest path between any two nodes, found by combining subtree heights at every node.

The idea

The diameter is the length of the longest path between two nodes anywhere in the tree, and that path does not have to pass through the root. Computing height bottom-up gives everything needed: at each node, the longest path through it is the height of its left subtree plus the height of its right subtree. Track the best value seen at any node while the heights are computed.

Code

public static int Diameter(TreeNode node, int[] best) {
    if (node == null) return 0;
    int left = Diameter(node.left, best);
    int right = Diameter(node.right, best);
    best[0] = Math.Max(best[0], left + right);
    return 1 + Math.Max(left, right);
}

Tips

• The path length is measured in edges, so two subtree heights l and r combine to l + r edges through that node.
• This reuses the exact "ask the children, combine, return" shape from computing height.

In the .NET library

A common bug is only checking the diameter at the root. The longest path can live entirely inside one subtree, so every node must be checked, not just the root.