Path Sum - Leetcode Solution

The Path Sum problem on LeetCode is to determine if a given binary tree has a root-to-leaf path such that the sum of all the values along the path equals the given target sum.

Here's the approach we can follow to solve this problem:

Approach:

We can solve this problem recursively, as follows:

1. Base Case: If the root is null, return False; if we have reached a leaf node, check if the target sum equals the value of the leaf node. If it does, return True; else return False.
2. Recursive Case: If we're not at a leaf node and the root is not null, we must check if there exists a path from the root to one of its subtrees such that the sum of the path equals the given target sum. To do this, we subtract the current node's value from the target sum and recursively check if there exists a path that sums to the remaining value in either the left or the right subtree of the root.

The intuition behind this recursive approach is that we consider each node as the root of a sub-tree and check if there exists a path from that root to a leaf node such that the path sum equals the target sum. We iterate over all nodes in the tree recursively and keep trying to check if there exists a path that equals the target sum.

Here's the Python code that implements this approach:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def hasPathSum(self, root: TreeNode, targetSum: int) -> bool:
        # Base Case: Empty tree or leaf node with value equal to target 
        if root is None:
            return False
        if root.left is None and root.right is None and root.val == targetSum:
            return True
        
        # Recursive case: check if there is a path that sums up to the targetSum
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree, since we visit each node once. The space complexity is also O(n), since the maximum amount of space used by the recursive call stack would be n in the case of a skewed tree.

1