Problem statement

Given the root of a binary tree with at least two nodes, call a node special when it is joined by an edge to exactly one other node. Every leaf is special; so is the root when it has only one child.

Return the largest sum of node values on a path that starts at one special node and ends at a different special node. Both ends count towards the sum.

Example 1

Input: root = [3,4,5,-10,4]
Output: 16
Explanation: The leaves are -10, 4 (under 4) and 5. The path 4 → 4 → 3 → 5 adds up to 16.

Example 2

Input: root = [-15,5,6,-8,1,3,9,2,-3,null,null,null,null,null,0,null,null,null,null,4,-1,null,null,10]
Output: 27
Explanation: The best path runs from leaf 3 up through 6 and down 9 → 0 → -1 → 10: 3 + 6 + 9 + 0 + (-1) + 10 = 27.

Example 3

Input: root = [10,-3,null,4,5]
Output: 12
Explanation: The root has a single child, so it is special too: 10 → -3 → 5 gives 12.

Constraints

• 2 <= number of nodes <= 10^4
• -10^3 <= Node.val <= 10^3

Hints for Maximum Path Sum Between Two Leaves

1. Hint 1

   Every path between two leaves turns around at exactly one node — the one closest to the root. That node has a leaf below it on both sides.

2. Hint 2

   For each node compute the best sum of a path going down from it to a leaf. A node with two children can be the turning point: left best + right best + its value.

3. Hint 3

   A node with only one child cannot be a turning point; it just extends its child's best downward path. Handle the root separately: with one child it is itself an end, so pair it with the best downward path below it.

How to solve Maximum Path Sum Between Two Leaves

A leaf-to-leaf path climbs from one leaf to a turning node and descends to another leaf in its other subtree. So compute, for every node, the best root-to-leaf sum of its subtree going down; a node with two children combines both sides, and the root, when it has one child, is a leaf-like end of its own.

Approach

1. Let down(node) be the best sum of a path from node down to a leaf below it (the node itself if it is a leaf).
2. For a leaf, return its value.
3. For a node with two children: l = down(left), r = down(right); update the answer with l + r + node.val and return max(l, r) + node.val.
4. For a node with one child, return down(child) + node.val — it cannot be an endpoint or a turning point.
5. Call down(root). If the root has exactly one child, the root is special too: update the answer with down(root) itself, a path from the root to a leaf.

Why it works

Every valid path has a highest node. If both ends are below it, it has two children and the path is the best leaf path on each side — which l + r + val takes. Otherwise one end is the highest node itself; that can only happen at the root with one child, and the best such path is down(root). A downward path must end at a leaf, so a one-child node passes its only option up unchanged.

Complexity

• Time — O(n)
• Space — O(h) for the recursion

Pitfalls

• Clamping negative branches to 0 (as in the any-to-any path problem) is wrong here — both ends must be special nodes.
• A node with one child is not a turning point: using it with an empty side would end a path at a non-special node.
• Forgetting the single-child root misses paths that start at the root.

Reference solution

Python

from typing import Optional

def maxPathSum(root: Optional[TreeNode]) -> int:
    best = [float('-inf')]

    def down(node):
        if node.left is None and node.right is None:
            return node.val
        if node.left is not None and node.right is not None:
            l, r = down(node.left), down(node.right)
            best[0] = max(best[0], l + r + node.val)
            return max(l, r) + node.val
        return down(node.left if node.left is not None else node.right) + node.val

    top = down(root)
    if root.left is None or root.right is None:
        best[0] = max(best[0], top)  # the root is special too
    return best[0]

Java

public static int maxPathSum(TreeNode root) {
    int[] best = { Integer.MIN_VALUE };
    int top = leafDown(root, best);
    if (root.left == null || root.right == null) best[0] = Math.max(best[0], top); // the root is special too
    return best[0];
}

static int leafDown(TreeNode node, int[] best) {
    if (node.left == null && node.right == null) return node.val;
    if (node.left != null && node.right != null) {
        int l = leafDown(node.left, best), r = leafDown(node.right, best);
        best[0] = Math.max(best[0], l + r + node.val);
        return Math.max(l, r) + node.val;
    }
    return leafDown(node.left != null ? node.left : node.right, best) + node.val;
}

C++

int maxPathSum(TreeNode* root) {
    int best = INT_MIN;
    function<int(TreeNode*)> down = [&](TreeNode* node) -> int {
        if (!node->left && !node->right) return node->val;
        if (node->left && node->right) {
            int l = down(node->left), r = down(node->right);
            best = max(best, l + r + node->val);
            return max(l, r) + node->val;
        }
        return down(node->left ? node->left : node->right) + node->val;
    };
    int top = down(root);
    if (!root->left || !root->right) best = max(best, top); // the root is special too
    return best;
}

JavaScript

var maxPathSum = function(root) {
    var best = -Infinity;
    var down = function(node) {
        if (node.left === null && node.right === null) return node.val;
        if (node.left !== null && node.right !== null) {
            var l = down(node.left), r = down(node.right);
            best = Math.max(best, l + r + node.val);
            return Math.max(l, r) + node.val;
        }
        return down(node.left !== null ? node.left : node.right) + node.val;
    };
    var top = down(root);
    if (root.left === null || root.right === null) best = Math.max(best, top); // the root is special too
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard
• Binary Tree Maximum Path Sum Hard