Path Sum

Problem:

Given a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Algorithm:

1. Keep track of nodes array to store the nodes that form the path with the target sum. Use a flag existsto indicate whether a valid path exists or not.
2. Traverse the binary tree and perform the following operations:
   1. At each node, add the node’s value to the running sum.
   2. When a leaf node is reached (both left and right children are null), check if the running sum is equal to targetSum.
      • If the sum is equal to targetSum, the current path is the answer. Return the nodes along with the value TRUE for the exists flag.
      • If the sum does not equal to targetSum, remove the current leaf node from nodes list and continue traversal.
3. Finally, return the exists flag and nodes array representing the path that sums to the targetSum.

This algorithm traverses the binary tree, calculating the sum of nodes along the path. When a leaf node is reached, it checks if the accumulated sum equals the target sum. If it does, it returns the path; if not, it continues traversing the other branches. The process is repeated until a valid path is found or all paths have been explored.

Solution & Visualize:

The animation/visualization below demonstrates how the algorithm works.

function checkIfPathExists(root, sum, targetSum, exists, pathNodes) {
    if (exists == 'TRUE') {
        return [exists, pathNodes];
    }

    if (root === null) return ['FALSE', pathNodes];

    sum += root.data;
    pathNodes.push(root);
    if (root.left === null && root.right === null) {
        if (sum == targetSum) {
            return ['TRUE', pathNodes];
        } else {
            pathNodes.pop();
            return ['FALSE', pathNodes];
        }
    }

    [exists, pathNodes] = checkIfPathExists(root.left, sum, targetSum, exists, pathNodes);
    [exists, pathNodes] = checkIfPathExists(root.right, sum, targetSum, exists, pathNodes);
    if (exists == 'FALSE') {
        pathNodes.pop();
    }

    return [exists, pathNodes];
}

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

let pathNodes = [];
[exists, pathNodes] = checkIfPathExists(root, 0, 23, 'FALSE', pathNodes);

let nodeValues = [];
pathNodes.forEach(node => {
    nodeValues.push(node.data);
});
console.log(exists, pathNodes) // TRUE - 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;
}