Maximum Sum Path

Problem:

Given a binary tree, find the maximum sum path from a leaf to a root.

Algorithm:

1. Keep track of maxSum and the nodes array. The nodes array will store the nodes that form the maximum sum path.
2. Traverse the tree, recursively calculating the sum of the left and right subtrees.
3. At each node, add the node’s value to the running sum and include the node in the currentPathNodes list.
4. When a leaf node is reached (both left and right children are null), compare the sum of the current path to the maxSum.
   1. If sum of the current path is greater than the maxSum, update maxSum to this new sum. And set the nodes array to currentPathNodes.
   2. If sum is less than the maxSum, remove this leaf from the currentPathNodes (pop the node) and continue traversing the other subtree.
5. Finally return the maxSum and nodes array representing the path of the maximum sum.

This algorithm recursively explores each path, tracking the sum and nodes involved. When a leaf node is reached, it checks if the current path has a greater sum than the previously recorded maximum. If so, it updates the maximum sum and the corresponding path.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

function findMaximumSumPath(root, sum, maxSum, currentPathNodes, nodes) {
    if (root === null) return [maxSum, nodes];

    sum += root.data;
    currentPathNodes.push(root);
    if (root.left === null && root.right === null) {
        if (sum > maxSum) {
            maxSum = sum;
            nodes = [...currentPathNodes];
            currentPathNodes.pop();
            return [maxSum, nodes];
        } else {
            currentPathNodes.pop();
            return [maxSum, nodes];
        }
    }

    [maxSum, nodes] = findMaximumSumPath(root.left, sum, maxSum, currentPathNodes, nodes);
    [maxSum, nodes] = findMaximumSumPath(root.right, sum, maxSum, currentPathNodes, nodes);
    currentPathNodes.pop();

    return [maxSum, nodes];
}

const nodes = [1,2,3,4,null,6,7,8,9,null,null,null,13];
const root = buildTree(nodes, 0, nodes.length);

let sum = 0;
let pathNodes = [];
let maxSum = 0;
[maxSum, pathNodes] = findMaximumSumPath(root, sum, maxSum, [], pathNodes);

let nodesData = [];
pathNodes.forEach((node) => {
    nodesData.push(node.data);
})

console.log(maxSum, nodesData); // 23, [1, 3, 6, 13]
                                        

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function buildTree(nodes, index, size) {
    if (index < size) {
        if (nodes[index] === null) {
            return null;
        }

        let root = new TreeNode(nodes[index]);
        root.left = buildTree(nodes, 2 * index + 1, size);
        root.right = buildTree(nodes, 2 * index + 2, size);

        return root;
    }

    return null;
}