Path Sum Ii

                                            
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> path;
        helper(root, targetSum, path, result);
        return result;
    }
    
    void helper(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
        if (root == NULL) return;
        
        path.push_back(root->val);
        
        if (root->left == NULL && root->right == NULL && targetSum == root->val) {
            result.push_back(path);
        }
        
        helper(root->left, targetSum - root->val, path, result);
        helper(root->right, targetSum - root->val, path, result);
        
        path.pop_back();
    }
};

                                            
import java.util.*;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int val) {
 *         this.val = val;
 *     }
 * }
 */

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        helper(root, targetSum, res, path);
        return res;
    }

    private void helper(TreeNode node, int targetSum, List<List<Integer>> res, List<Integer> path) {
        if (node == null) {
            return;
        }

        path.add(node.val);

        if (node.left == null && node.right == null && targetSum == node.val) {
            res.add(new ArrayList<>(path));
        } else {
            helper(node.left, targetSum - node.val, res, path);
            helper(node.right, targetSum - node.val, res, path);
        }

        path.remove(path.size() - 1);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
        var result = new List<IList<int>>();
        Helper(root, targetSum, new List<int>(), result);
        return result;
    }
    
    private void Helper(TreeNode node, int targetSum, List<int> path, List<IList<int>> result) {
        if (node == null) return;
        
        path.Add(node.val);
        if (node.left == null && node.right == null && node.val == targetSum) {
            result.Add(new List<int>(path));
        } else {
            Helper(node.left, targetSum - node.val, path, result);
            Helper(node.right, targetSum - node.val, path, result);
        }
        
        path.RemoveAt(path.Count - 1);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

var pathSum = function(root, targetSum) {
    const result = [];
    const DFS = (node, sum, path) => {
        if (!node) return;
        path.push(node.val);
        if (!node.left && !node.right && sum === node.val) {
            result.push([...path]);
        } else {
            DFS(node.left, sum - node.val, path);
            DFS(node.right, sum - node.val, path);
        }
        path.pop();
    };
    DFS(root, targetSum, []);
    return result;
};

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val === undefined ? 0 : val)
 *         this.left = (left === undefined ? null : left)
 *         this.right = (right === undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, targetSum: number): number[][] {
    const result: number[][] = [];

    const dfs = (node: TreeNode | null, currentPath: number[], pathSum: number) => {
        if (!node) return;

        currentPath.push(node.val);
        pathSum += node.val;

        if (!node.left && !node.right && pathSum === targetSum) {
            result.push([...currentPath]);
        }

        dfs(node.left, currentPath, pathSum);
        dfs(node.right, currentPath, pathSum);

        currentPath.pop();
    };

    dfs(root, [], 0);

    return result;
}

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) {
 *         $this->val = $value;
 *     }
 * }
 */
class Solution {
    
    /**
     * @param TreeNode $root
     * @param Integer $targetSum
     * @return Integer[][]
     */
    function pathSum($root, $targetSum) {
        $result = [];
        $path = [];
        $this->dfs($root, $targetSum, [], $result);
        return $result;
    }
    
    function dfs($node, $sum, $path, &$result) {
        if ($node === null) return;
        
        $path[] = $node->val;
        
        if ($node->left === null && $node->right === null && $sum === $node->val) {
            $result[] = $path;
            return;
        }
        
        $this->dfs($node->left, $sum - $node->val, $path, $result);
        $this->dfs($node->right, $sum - $node->val, $path, $result);
    }
}

                                            
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func pathSum(_ root: TreeNode?, _ targetSum: Int) -> [[Int]] {
        var result: [[Int]] = []
        var path: [Int] = []

        func dfs(_ node: TreeNode?, _ sum: Int) {
            guard let node = node else { return }
            path.append(node.val)

            if node.left == nil, node.right == nil, sum == node.val {
                result.append(path)
            }

            dfs(node.left, sum - node.val)
            dfs(node.right, sum - node.val)

            path.removeLast()
        }

        dfs(root, targetSum)
        return result
    }
}

                                            
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 
func pathSum(root *TreeNode, targetSum int) [][]int {
    var result [][]int
    var path []int
    var dfs func(*TreeNode, int)
    
    dfs = func(node *TreeNode, sum int) {
        if node == nil {
            return
        }
        
        path = append(path, node.Val)
        defer func() { path = path[:len(path)-1] }()
        
        if node.Left == nil && node.Right == nil && sum+node.Val == targetSum {
            temp := make([]int, len(path))
            copy(temp, path)
            result = append(result, temp)
            return
        }
        
        dfs(node.Left, sum+node.Val)
        dfs(node.Right, sum+node.Val)
    }
    
    dfs(root, 0)
    
    return result
}

                                            
# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left, @right = left, right
#     end
# end

def path_sum(root, target_sum)
    res = []
    dfs(root, target_sum, [], res)
    res
end

def dfs(node, target, path, res)
    return if node.nil?
    
    path << node.val
    if node.left.nil? && node.right.nil? && target == node.val
        res << path.clone
    else
        dfs(node.left, target - node.val, path, res)
        dfs(node.right, target - node.val, path, res)
    end
    
    path.pop
end

                                            
/**
 * Definition for a binary tree node.
 * class TreeNode(_value: Int = 0, _left: TreeNode = null, _right: TreeNode = null) {
 * }
 */

object Solution {
    def pathSum(root: TreeNode, targetSum: Int): List[List[Int]] = {
        var result: List[List[Int]] = List()

        def dfs(node: TreeNode, sumSoFar: Int, path: List[Int]): Unit = {
            if (node == null) return

            val newSum = sumSoFar + node.value
            val newPath = path :+ node.value

            if (node.left == null && node.right == null && newSum == targetSum) {
                result = result :+ newPath
            }

            dfs(node.left, newSum, newPath)
            dfs(node.right, newSum, newPath)
        }

        dfs(root, 0, List())
        result
    }
}

To solve this coding challenge of finding all root-to-leaf paths in a binary tree where the sum of node values equals a given targetSum, let's utilize Depth-First Search (DFS). We'll traverse the tree from the root to each leaf, keeping track of the cumulative path sum. If we reach a leaf node and the cumulative sum equals targetSum, we store that path. Let's break down the process in a detailed manner to understand each step.

Explanation

Understanding the Binary Tree Structure :

Each node in the tree has a value.
Each node can have a left child, a right child, both, or neither.

Concept of Root-to-Leaf Path :

A root-to-leaf path starts at the root node and proceeds downward to any leaf node.
A leaf node is defined as a node with no children.

Cumulative Path Sum :

As we traverse from the root to each leaf node, we accumulate the sum of the node values along the path.

Depth-First Search (DFS) Approach :

Using DFS, we explore each potential path from the root to a leaf.
We keep track of the current path and its accumulated sum.
If we reach a leaf node and the accumulated sum equals the targetSum, we store the path.

Handling Edge Cases :

If the tree is empty (root is null), there are no paths to consider.
Given the constraints, handle potentially large tree sizes efficiently.

Let's write out the detailed steps in pseudocode and include comments to explain each part:

Detailed Steps in Pseudocode

Initialization

Initialize Result Container :

Create a container (e.g., list) to store valid paths that meet the targetSum.

                                            
result = []

Define DFS Helper Function :

This function will take a node, remaining sum, and the current path as input parameters.

Defining the DFS Function

Base Case (Node is Null) :

If the current node is null, return immediately as there is nothing to process.

                                            
function DFS(node, remainingSum, currentPath):
if node is null:
return

Include Current Node in Path :

Append the current node's value to the current path.

                                            
add node.val to currentPath

Leaf Node Check :

Determine if the current node is a leaf node (no children).
Check if the remaining sum matches the current node's value.

Valid Path Condition :

If it’s a leaf node and the remaining sum equals the node’s value, store the current path.

                                            
if node is a leaf and remainingSum equals node.val:
append a copy of currentPath to result

Recursive DFS Calls :

Recursively invoke DFS on the left child and right child, adjusting the remaining sum.

                                            
DFS(node.left, remainingSum - node.val, currentPath)
DFS(node.right, remainingSum - node.val, currentPath)

Backtrack :

Remove the current node value from the path to backtrack for other potential paths.

                                            
remove the last element from currentPath

Main Function

Invoke DFS from Root :

Call the DFS helper function starting from the root node.
Return the result container storing all valid paths.

                                            
function pathSum(root, targetSum):
call DFS(root, targetSum, [])
return result

Complete Pseudocode

                                            
# Initialize result container to store all valid paths
result = []

# Define the DFS helper function
function DFS(node, remainingSum, currentPath):
    # Base case: if current node is null, return
    if node is null:
        return
    
    # Include current node's value in the path
    add node.val to currentPath
    
    # Check if the current node is a leaf node and if the remaining sum matches the node's value
    if node.left is null and node.right is null and remainingSum equals node.val:
        # Store the current path as a valid path
        append a copy of currentPath to result
    else:
        # Recurse on the left and right children with adjusted remaining sum
        DFS(node.left, remainingSum - node.val, currentPath)
        DFS(node.right, remainingSum - node.val, currentPath)
    
    # Backtrack: remove the current node's value from the path
    remove the last element from currentPath

# Define the main function to solve the problem
function pathSum(root, targetSum):
    # Start DFS from the root node with the targetSum
    call DFS(root, targetSum, [])
    # Return the collected valid paths
    return result

By following this detailed approach, we ensure that we explore all possible root-to-leaf paths, properly handle edge cases, and recursively traverse the tree with DFS while maintaining and backtracking the path as needed.