Diameter of Binary Tree

The diameter of a tree is the number of edges on the longest path between any two nodes.

Crucially, the path does NOT need to pass through the root. It could be entirely contained within the left or right subtree.

We use Post-Order DFS.

At any node, the longest path that bends at that node has left + right edges, where left and right are the heights of its two subtrees. The longest path overall can bend at any node, not only the root.

So:

1. Return Value: the height of the subtree, max(left, right) + 1 — a parent can extend only one side.
2. Side Effect: best = max(best, left + right).

Heights appear under nodes as they return. The longest path found so far is drawn in green, and it moves only when some node’s left + right beats it — often at a node that is not the root.