Diameter of Binary Tree

Problem

Given the root of a binary tree, return the length of the longest path between any two nodes in the tree. Path length is measured in edges, and the path is not required to pass through the root.

• The tree has between 1 and 30,000 nodes.
• Node values are integers and do not affect the answer.

Examples

• root = [6, 3, 9, 1, 4, None, 12, None, None, 2] → 5. The path 2 → 4 → 3 → 6 → 9 → 12 has five edges and happens to pass through the root.
• root = [10, 20] → 1. Two nodes, one edge.
• root = [5] → 0. A single node has no edges.

Hints

1. Every path has a unique highest node, the point where it stops going up and starts going down. Think about the path from that node's point of view.
2. At that highest node, how far can the path descend into the left subtree, and how far into the right?
3. Post-order DFS that returns each subtree's height and, as a side effect, updates a running maximum of height(left) + height(right).