Diameter of Binary Tree: the idea to remember.

The core insight

Return subtree height while updating a best path through each node using leftHeight + rightHeight.

Why it works

Every path has a highest node. At that node its two descending branches are bounded by the child heights.

The mistake to avoid

The longest path may not pass through the root. Reset accumulated state for each invocation.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

int diameterOfBinaryTree(TreeNode root) {
    int[] best = {0}; // Local state resets for every call.
    height(root, best);
    return best[0];
}
int height(TreeNode node, int[] best) {
    if (node == null) return 0;
    int l = height(node.left, best), r = height(node.right, best);
    best[0] = Math.max(best[0], l + r); // Diameter counts edges.
    return 1 + Math.max(l, r);
}

Make the next connection