Maximum path sum between two leaves of a binary tree

You are given the root of a binary tree. Every node stores an integer, which may be negative. A leaf is a node with no children.

A leaf-to-leaf path starts at one leaf, moves along parent/child edges without visiting any node twice, and ends at a different leaf. Its sum is the total of the values of every node on it, including both leaves.

Implement max_leaf_to_leaf_sum(root) -> int | None that returns the largest such sum. If the tree has fewer than two leaves, return None.

Constraints

• 1 to 10^5 nodes.
• -10^9 <= node value <= 10^9 (sums can exceed 32-bit range).
• The tree can be very unbalanced, up to 10^5 levels deep.

Example 1

        -50
       /   \
      4     1
     / \
    8   7

The best path is 8 -> 4 -> 7 with sum 19. Paths through the root, such as 8 -> 4 -> -50 -> 1 = -37, are worse.

Example 2

        0
       / \
    -100   3
     /
    2

The node -100 has one child, so it is not a leaf and a path cannot stop there. The only leaf-to-leaf path is 2 -> -100 -> 0 -> 3, with sum -95.

Aim for O(n) time.