deepSWE.io

Path Sum

TreesDFS

15 min

Problem Statement

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

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

Output: true

Solution: Depth-First Search (DFS)

The problem can be solved efficiently using a recursive Depth-First Search. We traverse the tree, subtracting the node's value from the `targetSum` at each step.

Algorithm Steps

Create a recursive function `hasPathSum(node, currentSum)`.
Base Case: If `node` is null, return `false`.
If the current node is a leaf node and its value equals the remaining `currentSum`, we've found a valid path.
Recursively call `hasPathSum` on the left and right children, passing the updated `currentSum`.

Path Found: false

Visiting node 5. Remaining sum: 17.

Path Sum Solution


# 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: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        if not root.left and not root.right and root.val == targetSum:
            return True
        
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)