Leetcode 112 – Path Sum

Problem: Leetcode 112 – Path Sum

Description:

Given the root of 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.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with sum 22 is 5 → 4 → 11 → 2.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There is no root-to-leaf path that sums to 5.

Example 3:

Input: root = [], targetSum = 0
Output: false

Analysis:

We need to determine whether there exists a path from the root of the tree to any leaf such that the sum of the node values along that path equals the given targetSum. This can be solved using depth-first search (DFS), where we recursively check each path and subtract the current node’s value from the targetSum as we traverse down the tree.

If at any point we reach a leaf node (a node with no children) and the remaining targetSum equals the value of the leaf node, we return true. If no such path is found, we return false.

Python Code:

def hasPathSum(root, targetSum):
    # Base case: If the tree is empty, return False
    if not root:
        return False

    # Check if we are at a leaf node, and if the remaining sum equals the leaf node value
    if not root.left and not root.right:
        return root.val == targetSum

    # Recursively check the left and right subtrees with the updated target sum
    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)

Example Usage:

# Example Tree: [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1], targetSum = 22
# Output: true (because 5 -> 4 -> 11 -> 2 sums to 22)

Time Complexity:

The time complexity is O(n), where n is the number of nodes in the tree. This is because we visit each node exactly once during the depth-first traversal.

Space Complexity:

The space complexity is O(h), where h is the height of the tree. In the worst case (for example, in a skewed tree), the recursion stack can go as deep as the height of the tree. In a balanced tree, the height is O(log n), but in the worst case, it can be O(n).