Path Sum

class Solution {
public:
    bool isPathSumEqual(TreeNode* root, int target) {
        if (root == nullptr) return false;
        std::stack<TreeNode*> stk_nodes;
        std::stack<int> stk_sums;
        stk_nodes.push(root);
        stk_sums.push(target - root->val);
        TreeNode* current_node;
        int current_sum;
        while (!stk_nodes.empty()) {
            current_node = stk_nodes.top();
            stk_nodes.pop();
            current_sum = stk_sums.top();
            stk_sums.pop();
            if (!current_node->left && !current_node->right && current_sum == 0)
                return true;
            if (current_node->right) {
                stk_nodes.push(current_node->right);
                stk_sums.push(current_sum - current_node->right->val);
            }
            if (current_node->left) {
                stk_nodes.push(current_node->left);
                stk_sums.push(current_sum - current_node->left->val);
            }
        }
        return false;
    }
};

Solution Summary:

This C++ solution approaches the problem of finding if there exists a root-to-leaf path in a binary tree that sums up to a given target value. Employ a depth-first search technique using two stacks, one to track nodes (stk_nodes) and another to track the remaining sum required to hit the target as the traversal proceeds (stk_sums).

• Initialize the stacks by pushing the root node and the residual sum (target minus root value).

• Iterate through the tree using a while loop that continues as long as there are nodes in stk_nodes.

• Within the loop:

  • Pop the top node from stk_nodes to work on it.
  • Pop the top value from stk_sums which represents the remaining sum required including the current node.
  • Check the following conditions to determine if a path sum equal to the target is found:
    • If the current node is a leaf (no left or right child) and the current_sum equals zero, return true.
  • If there's a right child, push it onto stk_nodes, and push current_sum decreased by the right child's value onto stk_sums.
  • Repeat the above step for the left child if it exists.

• If no such path is found by the end of the loop, return false.

This method efficiently handles the traversal without recursion by manually managing the stack, considering both the traversal path and the running sum calculations.

class Solution {
    public boolean checkPathSum(TreeNode root, int target) {
        if (root == null) return false;
    
        LinkedList<TreeNode> nodes = new LinkedList();
        LinkedList<Integer> values = new LinkedList();
        nodes.add(root);
        values.add(target - root.val);
    
        TreeNode current;
        int remainingSum;
        while (!nodes.isEmpty()) {
            current = nodes.pollLast();
            remainingSum = values.pollLast();
            if (
                (current.right == null) && (current.left == null) && (remainingSum == 0)
            ) return true;
    
            if (current.right != null) {
                nodes.add(current.right);
                values.add(remainingSum - current.right.val);
            }
            if (current.left != null) {
                nodes.add(current.left);
                values.add(remainingSum - current.left.val);
            }
        }
        return false;
    }
}

The provided Java solution targets the problem of determining whether there exists a path in a binary tree that sums up to a target value.

• Begin by defining a class Solution that includes the method checkPathSum, which accepts the binary tree's root and the target sum as parameters.

• Utilize two LinkedList instances:

  • nodes keeps track of tree nodes.
  • values holds the difference between the target sum and the cumulative value of nodes leading to the current node.

• Traverse the tree in a non-recursive manner using a loop, removing the last node and its corresponding value from these linked lists. Check each node:

  • If it's a leaf node (both children are null) and the remaining sum equals zero, a valid path is found, and the method returns true.

• For non-leaf nodes, append their children to the linked lists and adjust the remaining sum accordingly by subtracting the value of these children.

• If the loop completes without finding a valid path, return false.

This method efficiently explores each potential path using a Depth-First Search-like approach, storing and updating possible sums dynamically to determine if the target path sum exists in the binary tree.

bool checkPathSum(struct TreeNode *rootNode, int targetSum) {
    struct TreeNode *stackNodes[1000];
    int neededSums[1000];
    int top = 0;
    if (rootNode == NULL) return false;
    stackNodes[top] = rootNode;
    neededSums[top++] = targetSum - rootNode->val;
    while (top > 0) {
        struct TreeNode *current = stackNodes[--top];
        targetSum = neededSums[top];
        if (current->left == NULL && current->right == NULL && targetSum == 0) return true;
        if (current->right != NULL) {
            stackNodes[top] = current->right;
            neededSums[top++] = targetSum - current->right->val;
        }
        if (current->left != NULL) {
            stackNodes[top] = current->left;
            neededSums[top++] = targetSum - current->left->val;
        }
    }
    return false;
}

In the provided C program, the challenge is to determine if a binary tree has a root-to-leaf path that, when summed, equals a given target value. This solution makes use of depth-first search (DFS), specifically leveraged through a manual stack implementation to avoid recursion.

Here's how the function checkPathSum operates:

• Initialize necessary data structures: a stack to keep track of nodes (stackNodes) and an array to remember the sum needed when visiting each node (neededSums).
• Check if the root node is NULL early on to handle an empty tree scenario by returning false.
• Start by adding the root node and the adjusted target sum (initial target sum minus the root node's value) to their respective stack and array.
• Use a loop to iterate as long as there are nodes left in the stack:
  • Pop the node at the top of the stack and the current required sum.
  • If the node has no children (it's a leaf) and the remaining sum to reach the target sum is zero, return true since a valid path is found.
  • If the node has a right child, push this child to the stack and update the required sum considering this child's value.
  • Similarly, handle the left child.
• If all nodes are checked and no valid path sum is found, return false.

This method efficiently traces potential paths from root to leaf and compares each path's sum against the target without recursive overhead, using implicit stack manipulation to backtrack and traverse the tree properly.

var checkPathSum = function (node, target) {
    if (!node) return false;
    let nodes = [];
    let values = [];
    nodes.push(node);
    values.push(target - node.val);
    while (nodes.length > 0) {
        let current = nodes.pop();
        let tempSum = values.pop();
        if (!current.left && !current.right && tempSum === 0)
            return true;
        if (current.right) {
            nodes.push(current.right);
            values.push(tempSum - current.right.val);
        }
        if (current.left) {
            nodes.push(current.left);
            values.push(tempSum - current.left.val);
        }
    }
    return false;
};

The provided JavaScript code defines a function checkPathSum that determines whether there is a root-to-leaf path in a binary tree such that the sum of the node values along the path equals a given target sum.

• Initialize the algorithm by checking if the passed node is null. If it is, return false since no path exists.
• Utilize two arrays nodes and values to track the traversed nodes and the remaining sum needed to reach the target as you traverse the tree.
• Begin the tree traversal by adding the root node to nodes and the adjusted target sum (target minus the root node's value) to values.
• Use a while loop to process each node until no nodes remain:
  • Extract the last node from nodes and the corresponding sum from values.
  • Check if the current node is a leaf (no left or right child). If so, and if the sum is zero, a path that matches the target sum has been found, and true is returned.
  • If the node has a right child, push this child onto nodes and adjust the remaining sum accordingly in values.
  • Repeat the same for the left child if present.
• If no path matching the target sum is found by the end of the traversal, return false.

This solution efficiently checks for a path sum using a depth-first search approach without recursion, utilizing iterative logic with stacks to inspect each potential path in the tree.

class Solution:
    def pathSumExists(self, node: TreeNode, target: int) -> bool:
        if not node:
            return False
    
        stack = [
            (node, target - node.val),
        ]
        while stack:
            current, sum_left = stack.pop()
            if not current.left and not current.right and sum_left == 0:
                return True
            if current.right:
                stack.append((current.right, sum_left - current.right.val))
            if current.left:
                stack.append((current.left, sum_left - current.left.val))
        return False

The provided Python solution defines a method named pathSumExists within a class Solution. This method determines if there exists a path in a binary tree where the sum of the values along the path equals a target sum provided to the function.

• Begin by checking if the current node is None. If it is, return False because a non-existent node doesn't contribute to the sum.
• Initialize a stack with a tuple containing the root node and the adjusted sum which is the target sum minus the value of the root node.
• Enter a loop that continues as long as there are elements in the stack.
  • Pop the top element from the stack to get the current node and the remaining sum required to reach the target from that path.
  • Check if the current node is a leaf (no left or right child) and if the remaining sum required is zero. If both conditions are true, return True indicating a path sum exists.
  • If there is a right child, push it onto the stack and update the remaining sum needed by subtracting the value of the right child.
  • Similarly, push the left child onto the stack with the updated sum if the left child exists.
• If the loop completes without finding any path that meets the criteria, return False.

This approach uses depth-first search (DFS) and utilizes a stack to manage the traversal while adjusting the required sum as it navigates through the tree. Each node in the tree is processed to check potential paths from the node downwards, leveraging the stack for backtracking up the tree when necessary.