Binary Tree Maximum Path Sum - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT = 'current', CURRENT_COLOR = 'blue';
const PROCESSING = 'processing', PROCESSING_COLOR = 'orange';
const COMPUTED = 'computed', COMPUTED_COLOR = 'green';

function visMainFunction(treeInput) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startBatch();
    const root = convertInputToTree(treeInput);
    const tree = new VisBinaryTree(root, { dataPropName: 'val' });

    let globalMaxPathSum = -Infinity;
    makeVisVariable(globalMaxPathSum).options({ label: 'globalMaxPathSum' }).createVis(); 
    endBatch();

    function calculateMaxGainAndUpdateMaxPathSum(node, tree) {
        if (!node) return 0;

        const vm = tree.makeVisManagerForNode(node);

        startPartialBatch();
        setAsCurrentNode(node, tree);
        vm.addClass(PROCESSING);
        notification(`
            🔵 Processing the ${makeColoredSpan('current node', CURRENT_COLOR)}:
            <br>
            Calculating <b>left</b> and <b>right</b> max gains to determine:
            <ul>
                <li>how much each side can contribute if this node acts as the <b>pivot</b> (for clarity, we treat the <i>highest node on the path</i> as the pivot—even when no actual turn occurs), and</li>
                <li>which <b>single branch</b> (left or right) should be carried upward to the parent if it <i>isn’t</i> the pivot.</li>
            </ul>
            Only <b>one</b> node on any valid path can serve as the pivot — this step prepares both possibilities.
            <br><br>
            🔁 Recursive calls apply the same logic to descendants so each part of the tree contributes its best local result before rolling up to the global maximum.
        `);
        endBatch();

        const leftGain = calculateMaxGainAndUpdateMaxPathSum(node.left, tree);
        const rightGain = calculateMaxGainAndUpdateMaxPathSum(node.right, tree);

        const localPivotMaxPathSum = node.val + leftGain + rightGain;
        const maxSingleBranchPathSum = node.val + Math.max(leftGain, rightGain);
        const maxGainToParent = Math.max(maxSingleBranchPathSum, 0);

        startPartialBatch();
        setAsCurrentNode(node, tree);

        globalMaxPathSum = Math.max(globalMaxPathSum, localPivotMaxPathSum);

        notification(`
            ✅ Finished processing the ${makeColoredSpan('current node', CURRENT_COLOR)}.
            <ul>
                <li>⬅️ <b>Left gain</b>: <code>${leftGain}</code></li>
                <li>➡️ <b>Right gain</b>: <code>${rightGain}</code></li>
                <li>
                💥 <b>As pivot</b> (the <b>highest point</b> of this path — considered as pivot for simplicity even when no turning occurs, may use both sides):  
                <code>localPivotMaxPathSum = nodeVal(${node.val}) + leftGain(${leftGain}) + rightGain(${rightGain}) = ${localPivotMaxPathSum}</code><br>
                We update <code>globalMaxPathSum</code> with this if it’s larger.
                </li>
                <li>
                📤 <b>Returned to parent</b> (single-branch case):  
                <code>maxSingleBranchPathSum = nodeVal(${node.val}) + max(leftGain(${leftGain}), rightGain(${rightGain})) = ${maxSingleBranchPathSum}</code><br>
                <code>maxGainToParent = max(${maxSingleBranchPathSum}, 0) = ${maxGainToParent}</code> &nbsp; (drop if negative)
                </li>
                <li>
                📈 ${globalMaxPathSum === localPivotMaxPathSum
                    ? '<b>Global max updated!</b>'
                    : 'Global max remains at ' + globalMaxPathSum}
                </li>
            </ul>
            <div style="margin-top:6px">
                <i>Why two numbers?</i> — <b>Only one node can serve as the pivot on any valid path.</b><br>
                At each node, we compute the best path that’s pivoted at the current node — this value updates the global maximum if it’s the largest found so far.  
                However, when returning to the parent, the current node can no longer act as the pivot, so it returns only a single-branch gain (left or right), or <code>0</code> if both gains are negative.  
                This ensures ancestors can form their own pivoted paths independently, without reusing nodes.
            </div>
        `);

        node.val = `RV: ${maxGainToParent}`; // the original algorithm does not require updating the node value here, this is done just for the sake of animation 
        vm.removeClass(PROCESSING).addClass(COMPUTED);
        endBatch();

        return maxGainToParent;
    }

    calculateMaxGainAndUpdateMaxPathSum(root, tree);

    notification(`🏁 <b>Done!</b> The <b>maximum path sum</b> is: <b>${globalMaxPathSum}</b>`);
    return globalMaxPathSum;
}

let current = null;

function setAsCurrentNode(node, tree) {
    startBatch();
    if (current) tree.makeVisManagerForNode(current).removeClass(CURRENT);
    tree.makeVisManagerForNode(node).addClass(CURRENT);
    current = node;
    endBatch();
}

function initClassProperties() {
    setClassProperties(CURRENT, { borderColor: CURRENT_COLOR });
    setClassProperties(PROCESSING, { backgroundColor: PROCESSING_COLOR });
    setClassProperties(COMPUTED, { backgroundColor: COMPUTED_COLOR });
}

function convertInputToTree(arr) {
    if (!arr.length || arr[0] === null) return null;
    const nodes = arr.map(val => (val === null ? null : new TreeNode(val)));
    for (let i = 0; i < arr.length; i++) {
        if (nodes[i]) {
            nodes[i].left = nodes[2 * i + 1] || null;
            nodes[i].right = nodes[2 * i + 2] || null;
        }
    }
    return nodes[0];
}

function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    🎨 <b>Visual Cues:</b>
    <ul>
      <li>${makeColoredSpan(CURRENT_COLOR + ' border', CURRENT_COLOR)} → marks the <b>current node</b> being processed.</li>
      <li>${makeColoredSpan(PROCESSING_COLOR + ' background', PROCESSING_COLOR)} → node is <b>in progress</b> while its gains are being computed.</li>
      <li>${makeColoredSpan(COMPUTED_COLOR + ' background', COMPUTED_COLOR)} → node’s work is <b>completed</b>; its label shows <code>RV: &lt;maxGainToParent&gt;</code> (the value returned upward).</li>
    </ul>
  `);
}

Approach

We solve this using a single DFS traversal, where each node computes two key quantities. Before diving into those, let’s recall the definition of a path in this problem:

📖 A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can appear in the sequence at most once, and the path does not need to pass through the root.

Based on the path definition, any valid path can “turn” at most once — at a single node where traversal switches from one branch to another. We call that turning point the pivot. For simplicity, we’ll still use the term pivot even when one side is empty and no actual turn occurs — in either case, the pivot is the highest (closest-to-root) node on the path. Conceptually, the pivot is the only node that can combine contributions from both sides (when both child gains > 0); all other nodes on the path can contribute from only one side (left or right). Therefore, each valid path has exactly one pivot, serving as its rotation point.

Therefore, each node computes the quantities below:

1️⃣ Local “pivoted” path sum (as if this node is the pivot)
The best path that passes through the current node and is allowed to use both children:
localPivotMaxPathSum = node.val + leftGain + rightGain
This represents the maximum path sum that includes this node as the single pivot — the rotation point connecting both sides. We use this value to update the global maximum if it yields a better result than previously found paths.
2️⃣ Gain returned to the parent
Once we return to the parent, the current node can no longer act as the pivot. It passes up only a single-branch gain — its value plus the higher of its left or right gains:
maxGainToParent = max(maxSingleBranchPathSum, 0)
Here, maxSingleBranchPathSum = node.val + max(leftGain, rightGain) represents the best non-pivot (no rotation) path rooted at the current node that continues through only one child (left or right). If this sum is negative, we return 0 — meaning this node doesn’t contribute upward to its parent. Each child’s gain is already non-negative, since any negative branch was clamped to 0 during its own recursion.

Why two numbers? — Because each valid path can include only one pivot. Therefore, at each node we:

Compute the best path that’s pivoted at the current node — to check if it improves the global maximum.
Return only a single-branch gain to the parent — allowing ancestors to form their own pivoted paths independently, while getting the maximum contribution from this node.

🔁 DFS Recurrence

function maxGain(node):
    if node is null: return 0
    leftGain  = maxGain(node.left)
    rightGain = maxGain(node.right)

    localPivotMaxPathSum = node.val + leftGain + rightGain
    globalMaxPathSum = max(globalMaxPathSum, localPivotMaxPathSum)

    maxSingleBranchPathSum = node.val + max(leftGain, rightGain)
    return max(maxSingleBranchPathSum, 0) // calculate and return the maxGainToParent

📘 Variable Summary

localPivotMaxPathSum — best path sum through this node (pivoted here, allowed to use both sides).
maxSingleBranchPathSum — best single-branch gain returned to the parent (non-pivot contribution).
maxGainToParent — maxSingleBranchPathSum after dropping if negative.
globalMaxPathSum — overall best pivoted path found in the entire tree.

Time Complexity

O(n), where n is the number of nodes — each node is visited once.

Space Complexity

O(h), where h is the tree height — the maximum recursion stack size is proportional to the tree height.

Input-1

Binary Tree Maximum Path Sum - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🔁 DFS Recurrence

📘 Variable Summary

Time Complexity

Space Complexity