Return the Minimum-Sum Root-to-Leaf Path

Problem Statement

Given the root of a binary tree where each node holds an integer value, return the values along the root-to-leaf path that yields the minimum total sum.

A root-to-leaf path starts at the root and ends at any leaf node (a node with no children). If multiple root-to-leaf paths have the exact same minimum sum, break ties deterministically by selecting the leftmost path (i.e., prioritize visiting left child branches before right child branches).

Your solution must handle trees with up to 100,000 nodes, including completely skewed trees (e.g., a linked list), without causing stack overflow errors.

Function Signature

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def min_sum_path(root: Optional[TreeNode]) -> List[int]:
    pass

Examples

Example 1

       5
      / \
     2   -3
    / \    \
   1   4    2

• Path 1: 5 -> 2 -> 1, sum = 8
• Path 2: 5 -> 2 -> 4, sum = 11
• Path 3: 5 -> -3 -> 2, sum = 4

Output: [5, -3, 2]
Explanation: The path 5 -> -3 -> 2 has the lowest sum (4).

Example 2

       1
      / \
     2   2

• Path 1: 1 -> 2 (left leaf), sum = 3
• Path 2: 1 -> 2 (right leaf), sum = 3

Output: [1, 2]
Explanation: Both paths have sum 3. By the tie-break rule, the leftmost path is chosen.

Constraints

• The number of nodes in the tree is in the range [0, 100_000].
• -10^9 <= Node.val <= 10^9
• An empty tree (root = None) should return an empty list [].
• The tree may be heavily skewed. Recursive solutions relying on the default Python recursion limit will fail.