Path Sum II

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

• We are given a binary tree and a target sum.
• We need to find all root-to-leaf paths in the tree where the sum of the nodes' values along the path equals the target sum.
• A path is defined as a sequence of nodes from the root to a leaf node, and the sum of their values should equal the target sum.

2. Analyze the problem: To solve this problem, we can use depth-first search (DFS) to traverse the tree and keep track of the current path and its sum. We can store the paths that satisfy the target sum and return them as the result.

3. Design an algorithm: Here is the algorithm to solve the problem:

1. Define a function pathSumHelper(node, target, path, result):
   • If node is null, return.
   • Add the current node's value to the current path sum.
   • Append the current node to the current path.
   • If node is a leaf node (both left and right children are null) and the current path sum equals the target sum:
     • Add the current path to the result list.
   • Recursively call pathSumHelper for the left child with the updated path and path sum.
   • Recursively call pathSumHelper for the right child with the updated path and path sum.
   • Remove the current node from the current path.
   • Subtract the current node's value from the current path sum.
2. Initialize an empty result list.
3. Call pathSumHelper(root, targetSum, [], result).
4. Return the result list.

4. Explain your approach: The approach involves using depth-first search (DFS) to traverse the tree. We maintain a current path and its sum as we traverse the tree. Whenever we reach a leaf node and the current path sum equals the target sum, we add the current path to the result list. By using a recursive helper function, we can explore all possible paths and collect the valid ones.

5. Write clean and readable code:

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def pathSum(root, targetSum):
    def pathSumHelper(node, target, path, result):
        if not node:
            return

        pathSum = target - node.val
        path.append(node.val)

        if not node.left and not node.right and pathSum == 0:
            result.append(path[:])

        pathSumHelper(node.left, pathSum, path, result)
        pathSumHelper(node.right, pathSum, path, result)

        path.pop()

    result = []
    pathSumHelper(root, targetSum, [], result)
    return result

6. Test your code: Let's test the code with different test cases to ensure its correctness:

1. Test case with an empty tree:

   • Input: root = None, targetSum = 0
   • Expected output: []

2. Test case with a single node tree:

   • Input: root = TreeNode(5), targetSum = 5
   • Expected output: [[5]]

3. Test case with a tree containing multiple paths:

   • Input: root = TreeNode(1, TreeNode(2), TreeNode(3)), targetSum = 3
   • Expected output: [[1, 2]] (as the path [1, 2] has a sum of 3)

7. Optimize if necessary: The solution already has a time complexity of O(N), where N is the number of nodes in the tree, since we need to visit each node once. The space complexity is O(H), where H is the height of the tree, as we store the paths in a result list. This solution is already efficient and does not require further optimization.

8. Handle error cases: The code handles the case where the input tree is empty. It returns an empty list as the output in that case.

9. Discuss complexity analysis: The time complexity of the solution is O(N), where N is the number of nodes in the tree. We need to visit each node once. The space complexity is O(H), where H is the height of the tree. In the worst case, the height of the tree can be N (for a skewed tree), so the space complexity can be O(N) in the worst case. The solution has a linear time complexity and linear space complexity.