Diameter of Binary Tree

The diameter of a binary tree is the length of the longest path between any two nodes, counted in edges. The path does not have to pass through the root.

Tree format. A binary tree is given on one line in level order (top to bottom, left to right), with null for a missing child — the same way most interview platforms show trees. Trailing nulls are left out, and an empty tree is the single word null. Example: 3 9 20 null null 15 7 is

    3
   / \
  9   20
     /  \
    15   7

Input: one tree (at least one node).

Output: the diameter.

Constraints: 1 ≤ nodes ≤ 10⁴. The tree has at most 10⁴ nodes and its height is at most 500, so recursion is safe in every language.

Think about it: the longest path through a node is height(left) + height(right). Compute heights bottom-up and update a global maximum on the way — one O(n) pass instead of calling height from every node.