The tell: A global best that is computed at every node but returned differently upward.
How you get there
1The longest path through a node is leftDepth + rightDepth.
2But the value returned to the parent is 1 + max(left, right) — a path, not a diameter.
3Keep the best in an enclosing variable so one traversal answers both.
Solution
Python
def diameter_of_binary_tree(root) -> int:
best = 0
def depth(node) -> int:
nonlocal best
if not node:
return 0
left, right = depth(node.left), depth(node.right)
best = max(best, left + right) # path through this node
return 1 + max(left, right) # path down from this node
depth(root)
return best
Time
O(n)
Space
O(h)
What goes wrong
Returning left + right upward conflates the two quantities and gives wrong answers higher in the tree.