Path Sum

Introduction

The "Path Sum" problem is a binary tree-based problem where you are given the root of a binary tree and an integer target sum. The task is to determine whether there exists a root-to-leaf path such that the sum of the node values along the path equals the target sum. A root-to-leaf path is defined as a path that starts at the root and ends at a leaf node (a node with no children).

Problem Statement

Given the root of a binary tree and an integer target sum, return true if there is a root-to-leaf path such that the sum of the values along the path equals the target sum, and false otherwise.

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

The tree node structure is given above. The goal is to return whether there exists a root-to-leaf path whose sum is equal to the target sum.

Approach

To solve this problem, we can use depth-first search (DFS) to traverse the tree. At each node, we check if the current node can contribute to a path that sums up to the target sum. We subtract the value of the current node from the target sum and recursively check the left and right subtrees.

• Start by performing a DFS traversal from the root node.
• At each node, subtract the node's value from the remaining sum and check the left and right subtrees.
• If a leaf node is reached and the remaining sum equals zero, return true.
• If no such path is found after the traversal, return false.

Algorithm

The algorithm follows these steps:

1. Define a helper function that performs a DFS traversal while maintaining the remaining sum.
2. At each node, subtract the node's value from the remaining sum.
3. If the node is a leaf node and the remaining sum equals zero, return true.
4. If there is no valid path in the left or right subtrees, return false.
5. Return false if no valid path is found after exploring both subtrees.

This approach ensures that we check all paths from the root to the leaf nodes and find if there exists one that matches the target sum.

Example

Consider the following binary tree and target sum of 22:

             5
            / \
           4   8
          /   / \
         11  13  4
        /  \      \
       7    2      1
        

In this example, the following root-to-leaf paths have a sum of 22: - Path 1: 5 → 4 → 11 → 2 (sum = 22) - Path 2: 5 → 8 → 4 → 1 (sum = 22)

Therefore, the solution should return true because there exists at least one valid root-to-leaf path where the sum is equal to 22.

Code Implementation

Below is the Python implementation of the algorithm to check if there exists a root-to-leaf path that sums up to the target sum:

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

def hasPathSum(root, target):
    if not root:
        return False
    
    # Subtract the node's value from the target sum
    target -= root.val
    
    # If it's a leaf node, check if the target sum is zero
    if not root.left and not root.right:
        return target == 0
    
    # Recursively check the left and right subtrees
    return hasPathSum(root.left, target) or hasPathSum(root.right, target)
        

In this code: - The `hasPathSum` function is a recursive helper that performs a depth-first search to explore all root-to-leaf paths. - At each node, we subtract the current node's value from the target sum. - If a leaf node is reached and the target sum becomes zero, we return true indicating that the path sum matches the target. - If no such path is found after exploring both subtrees, we return false.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. In the worst case, we must visit each node once during the DFS traversal.

The space complexity is O(h), where h is the height of the tree. This space is used by the recursion stack during the DFS traversal. In the worst case, the height of the tree is O(n) (for a skewed tree), and in the best case, it is O(log n) (for a balanced tree).

Conclusion

The "Path Sum" problem is a classic example of using depth-first search (DFS) to explore all possible paths in a binary tree and checking if any of them sum up to a given target. By using recursion, we efficiently check all root-to-leaf paths for the desired sum, making this approach both simple and effective.