Path Sum

Difficulty: Easy | Acceptance: 54.90% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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.

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search
• Breadth-First Search

Examples

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 the target sum is shown with bold type in the image (5 -> 4 -> 11 -> 2).

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There are two root-to-leaf paths in the tree:
1 -> 2 (sum = 3) and 1 -> 3 (sum = 4).

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Recursive Depth-First Search

Intuition We can traverse the tree recursively, subtracting the current node’s value from the target sum as we go down. If we reach a leaf node and the remaining sum equals the leaf’s value, we have found a valid path.

Steps

• If the root is null, return false.
• Check if the current node is a leaf (both left and right children are null).
• If it is a leaf, return true if the remaining targetSum equals the node’s value.
• If it is not a leaf, recursively call the function on the left and right children, subtracting the current node’s value from targetSum.
• Return true if either the left or right subtree returns true.

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        if not root.left and not root.right:
            return targetSum == root.val
        
        remaining_sum = targetSum - root.val
        return self.hasPathSum(root.left, remaining_sum) or self.hasPathSum(root.right, remaining_sum)

Complexity

• Time: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
• Space: O(H), where H is the height of the tree. This is due to the recursion stack. In the worst case (skewed tree), H = N. In the best case (balanced tree), H = log N.
• Notes: This is the most intuitive approach for tree problems involving paths.

Iterative Depth-First Search

Intuition We can simulate the recursion using a stack. We store pairs of nodes and the remaining sum required to reach the target from that node downwards.

Steps

• Initialize a stack with the root node and the targetSum.
• While the stack is not empty:
  • Pop a node and the current sum from the stack.
  • If the node is a leaf, check if the current sum equals the node’s value. If so, return true.
  • If the node has a right child, push the right child and the updated sum (current sum - node value) onto the stack.
  • If the node has a left child, push the left child and the updated sum onto the stack.
• If the loop finishes without finding a path, return false.

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        stack = [(root, targetSum)]
        
        while stack:
            node, current_sum = stack.pop()
            
            if not node.left and not node.right:
                if current_sum == node.val:
                    return True
            
            if node.right:
                stack.append((node.right, current_sum - node.val))
            if node.left:
                stack.append((node.left, current_sum - node.val))
        
        return False

Complexity

• Time: O(N), where N is the number of nodes in the tree.
• Space: O(H), where H is the height of the tree. The stack stores at most the depth of the tree.
• Notes: This approach avoids recursion stack overflow issues for very deep trees, though it is slightly more verbose.

Breadth-First Search

Intuition We traverse the tree level by level using a queue. Instead of tracking the remaining sum needed, we track the cumulative sum from the root to the current node.

Steps

• Initialize a queue with the root node and its value.
• While the queue is not empty:
  • Dequeue a node and the current cumulative sum.
  • If the node is a leaf, check if the cumulative sum equals the targetSum. If so, return true.
  • If the node has a left child, enqueue the left child with the updated sum (current sum + left child’s value).
  • If the node has a right child, enqueue the right child with the updated sum (current sum + right child’s value).
• If the loop finishes, return false.

from collections import deque

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        queue = deque([(root, root.val)])
        
        while queue:
            node, current_sum = queue.popleft()
            
            if not node.left and not node.right:
                if current_sum == targetSum:
                    return True
            
            if node.left:
                queue.append((node.left, current_sum + node.left.val))
            if node.right:
                queue.append((node.right, current_sum + node.right.val))
        
        return False

Complexity

• Time: O(N), where N is the number of nodes in the tree.
• Space: O(W), where W is the maximum width of the tree. In the worst case, this could be N/2 (for a full tree), which is roughly O(N).
• Notes: Useful if you want to find the shortest path (though not applicable here since all root-to-leaf paths have the same depth in terms of edges, but different sums).