Minimum root-to-leaf path sum

Given the root of a binary tree whose nodes hold integers (values may be negative), find the root-to-leaf path with the smallest sum.

A leaf is a node with no children. A root-to-leaf path starts at the root and ends at a leaf; its sum is the total of every node value on it. A node with only one child is not a leaf.

Implement:

def min_path(root: TreeNode | None) -> tuple[int | None, list[int]]:
    ...

Return the minimum sum and the node values along that path, from root to leaf. For an empty tree return (None, []). If several paths tie, return the leftmost one.

Constraints

• 0 to 10^5 nodes; the tree may be a single long chain.
• -10^4 <= node value <= 10^4.

Example 1

        10
       /  \
      5    7
       \  / \
       4 2   9
        /
      -3

Paths: 10-5-4 = 19, 10-7-2-(-3) = 16, 10-7-9 = 26. Output: (16, [10, 7, 2, -3]).

Example 2

    1
     \
      8

The root has a child, so it is not a leaf. The only path is 1-8. Output: (9, [1, 8]).

Start with the minimum sum alone, then return the path.

Reconstructed from the reported question; details may differ from what interviewers ask.