Maximum path sum between two leaves of a binary tree

A leaf-to-leaf path climbs from one leaf up to a single highest node (its
"apex"), then goes down to a different leaf. The apex must have two children,
one leaf in each subtree. So the answer is:

max over nodes with two children of
    node.val + best_down(node.left) + best_down(node.right)

where best_down(x) is the largest sum of a path that starts at x and goes
down to some leaf of x's subtree.

Brute force. For every two-child node, compute best_down of both
children with a fresh DFS. That is O(n) per node, O(n^2) on a skewed tree.

One post-order pass. Compute best_down bottom-up and use it at the
parent in the same pass:

• leaf: best_down = val
• one child c: best_down = val + best_down(c) (the path has no choice; it
  must keep going down to reach a leaf)
• two children: first update answer = max(answer, val + L + R), then
  best_down = val + max(L, R)

Invariants:

• best_down(x) always ends at a real leaf. A one-child node is not a leaf,
  so it never stops a path. This is the most common bug: treating a missing
  child as 0 or -inf and letting a path end at an internal node.
• Negative values are fine. We never "drop" a child because it is negative;
  both ends must be leaves, so a negative branch is taken if it is the only one.
• answer is only updated at two-child nodes, so it always describes two
  distinct leaves. If the tree has no two-child node it has at most one leaf,
  and we return None.

With up to 10^5 nodes the tree can be a chain 10^5 deep. Python's recursion
limit is far below that, so the code uses an explicit stack. Python ints do
not overflow; in Java/C++ use 64-bit (sums reach about 10^14).

from __future__ import annotations

from dataclasses import dataclass
from typing import Optional


@dataclass
class TreeNode:
    val: int
    left: Optional[TreeNode] = None
    right: Optional[TreeNode] = None


def max_leaf_to_leaf_sum(root: Optional[TreeNode]) -> Optional[int]:
    """Largest sum of a path between two distinct leaves, or None if the
    tree has fewer than two leaves."""
    if root is None:
        return None

    best_down: dict[int, int] = {}   # id(node) -> best node-to-leaf sum
    answer: Optional[int] = None

    # Iterative post-order: (node, children_done)
    stack: list[tuple[TreeNode, bool]] = [(root, False)]
    while stack:
        node, children_done = stack.pop()
        if not children_done:
            stack.append((node, True))
            if node.right:
                stack.append((node.right, False))
            if node.left:
                stack.append((node.left, False))
            continue

        left, right = node.left, node.right
        if left is None and right is None:
            best_down[id(node)] = node.val
        elif left is None or right is None:
            child = left if left is not None else right
            best_down[id(node)] = node.val + best_down.pop(id(child))
        else:
            lsum = best_down.pop(id(left))
            rsum = best_down.pop(id(right))
            through = node.val + lsum + rsum
            if answer is None or through > answer:
                answer = through
            best_down[id(node)] = node.val + max(lsum, rsum)

    return answer


def build(values: list[Optional[int]]) -> Optional[TreeNode]:
    """Build a tree from level-order values (LeetCode style, None = missing)."""
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    queue, i = [root], 1
    for node in queue:
        if i >= len(values):
            break
        if values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root


if __name__ == "__main__":
    assert max_leaf_to_leaf_sum(build([1, 2, 3])) == 6
    assert max_leaf_to_leaf_sum(build([5])) is None
    assert max_leaf_to_leaf_sum(build([1, 2, None, 3])) is None
    assert max_leaf_to_leaf_sum(build([-10, -2, -3])) == -15
    # Apex below the root: left subtree holds the best pair.
    assert max_leaf_to_leaf_sum(build([-50, 4, 1, 8, 7])) == 19
    # One-child node must not end a path: 2 -> -100 forces the left side.
    assert max_leaf_to_leaf_sum(build([0, -100, 3, 2])) == -95
    # Deep chain with a fork at the bottom (no recursion limit issues).
    root = node = TreeNode(1)
    for _ in range(100_000):
        node.left = TreeNode(1)
        node = node.left
    node.left, node.right = TreeNode(2), TreeNode(3)
    assert max_leaf_to_leaf_sum(root) == 6
    print("ok")

• Time: O(n). Each node is pushed twice and processed once.
• Space: O(h) for the stack plus the best_down entries of nodes whose parent
  is not finished yet, which is O(h) as well because entries are popped when
  the parent consumes them. Worst case O(n) for a chain, O(log n) for a
  balanced tree.

• [1, 2, 3] -> 6 (2 -> 1 -> 3).
• [5] (single node, one leaf) -> None.
• [1, 2, None, 3] (a chain, one leaf) -> None.
• [-10, -2, -3] -> -15 (all negative; both ends must still be leaves).
• [-50, 4, 1, 8, 7] -> 19 (8 -> 4 -> 7; the apex is not the root).
• [0, -100, 3, 2] -> -95 (left side is 0 -> -100 -> 2 because -100 has only
  one child and cannot be a path end; path 2 -> -100 -> 0 -> 3).
• A chain of 100,001 ones ending in a node with leaves 2 and 3 -> 6
  (checks the iterative traversal on a deep tree).
• Values at the bounds, e.g. two leaves of 10^9 under a root of 10^9 ->
  3 * 10^9 (would overflow 32-bit ints).

1. Return the path, not just the sum. Store, with each best_down, the
   leaf that achieves it (or a child pointer). At the best apex, walk down both
   chosen sides and join reverse(left_chain) + [apex] + right_chain.
2. Any node to any node (LeetCode 124). Allow paths to start and stop
   anywhere: best_down = val + max(0, L, R) and candidate
   val + max(0, L) + max(0, R) at every node. Contrast the two clearly.
3. Path between two given leaves / k specific nodes. Find the LCA and sum
   the two root-to-node paths minus the LCA counted once; with many queries,
   precompute prefix sums from the root and binary-lifting LCA so each query is
   O(log n).
4. N-ary tree. At each node keep the two largest child best_down values
   (top-2 in one scan); candidate is val + top1 + top2 when the node has at
   least two children.
5. The tree is too big for memory / streamed in post-order. The same
   algorithm works on a post-order stream with a stack of best_down values,
   since each node only needs its children's results.

Mid-level (L4)

• States that the path bends at one node and that the node needs two children.
• Writes a correct recursive post-order solution in O(n).
• Handles the single-child case correctly once prompted, and tests a small tree.

Senior (L5)

• Spots the one-child trap and negative values without prompting.
• Defines what to return with fewer than two leaves and says so up front.
• Notes recursion depth at 10^5 nodes and either goes iterative or explains
  how; mentions 64-bit sums for other languages.

Staff (L6+)

• Moves between variants (leaf-to-leaf, any-to-any, given endpoints) by
  changing only the recurrence, and explains why each choice is correct.
• Extends to path reconstruction and N-ary trees cleanly.
• Drives the test plan: chains, all-negative, apex below root, deep trees.