#112

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Path Sum

Determine if a binary tree has a root-to-leaf path where the sum of node values equals a given target sum, using DFS or BFS traversal techniques.

tree depth first search breadth first search binary tree

Problem Statement

Given the root of a binary tree and an integer targetSum, determine if there exists a root-to-leaf path where the sum of all node values equals targetSum. A leaf is defined as a node without any children, and the solution must correctly handle both empty trees and trees with negative or zero values. This problem tests your ability to traverse a tree while maintaining state information for each path.

You must return true if at least one root-to-leaf path satisfies the sum condition, and false otherwise. The solution should account for different tree shapes and values, using either depth-first search or breadth-first search to explore all potential paths efficiently, ensuring that leaf checks and cumulative sum tracking are correctly applied in every branch.

Examples

Example 1

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

Output: true

The root-to-leaf path with the target sum is shown.

Example 2

Input: root = [1,2,3], targetSum = 5

Output: false

There are two root-to-leaf paths in the tree: (1 --> 2): The sum is 3. (1 --> 3): The sum is 4. There is no root-to-leaf path with sum = 5.

Example 3

Input: root = [], targetSum = 0

Output: false

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

Solution Approach

Recursive Depth-First Search

Use a recursive DFS approach that passes the current cumulative sum down the tree. At each node, subtract the node value from the target and recursively check left and right children. If a leaf node is reached and the remaining sum equals zero, return true. This method naturally tracks the state along each path but requires careful handling of null children to avoid errors in empty or unbalanced trees.

Iterative Depth-First Search with Stack

Implement DFS iteratively using an explicit stack that stores tuples of nodes and their current path sums. Pop nodes from the stack, update the cumulative sum, and push children with their corresponding updated sums. If a leaf is encountered with a sum equal to the target, return true. This approach avoids recursion depth limits and allows fine-grained control over traversal order, but requires explicit management of node-sum pairs.

Breadth-First Search with Queue

Use BFS to traverse the tree level by level, storing nodes along with the sum accumulated to that node in a queue. Dequeue nodes iteratively, update the path sum, and enqueue children with their cumulative sums. When a leaf node matches the target sum, return true. BFS ensures all paths are explored systematically and can find the shortest path satisfying the sum, but requires more memory to store nodes and sums across each level of the tree.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on visiting each node once, giving O(n) for a tree with n nodes, while space complexity ranges from O(h) for DFS recursion to O(n) for BFS queue storage. Both provided complexities align with the traversal approach used, reflecting either stack depth or breadth-level memory requirements.

What Interviewers Usually Probe

Do you account for negative and zero values when calculating path sums?
Can you implement both DFS and BFS versions and explain their trade-offs in memory and recursion?
Will you correctly identify leaf nodes and handle empty or single-node trees in your solution?

Common Pitfalls or Variants

Common pitfalls

Failing to correctly check that a node is a leaf before comparing the sum to target can produce false positives.
Not handling null or empty trees leads to runtime errors or incorrect false results.
Overwriting or mismanaging cumulative sums in recursive DFS can cause wrong answers when multiple paths exist.

Follow-up variants

Find all root-to-leaf paths that sum to target instead of a boolean output.
Return the number of root-to-leaf paths that sum to the target value.
Determine if any path (not necessarily root-to-leaf) sums to target, allowing mid-tree endpoints.

FAQ

What is the main idea behind the Path Sum problem?

The goal is to determine if a root-to-leaf path exists where the sum of node values equals the target. It focuses on binary tree traversal while maintaining the cumulative sum state.

Can both DFS and BFS be used for this problem?

Yes, recursive DFS explores paths deeply, while BFS examines nodes level by level. Both track cumulative sums, but DFS uses stack memory, and BFS uses a queue.

How should leaf nodes be handled in Path Sum?

Leaf nodes must be identified correctly, as the target sum check only applies at leaves. Intermediate nodes matching the sum do not count.

What are common errors when implementing Path Sum?

Common mistakes include forgetting leaf checks, mishandling null trees, or incorrectly updating cumulative sums, leading to false positives or runtime errors.

Can Path Sum handle negative and zero node values?

Yes, the solution should account for negative and zero values since paths with these can still sum to the target, requiring careful state tracking.

terminal

Solution

Solution 1: Recursion

Starting from the root node, recursively traverse the tree and update the value of the node to the path sum from the root node to that node. When you traverse to a leaf node, determine whether this path sum is equal to the target value. If it is equal, return `true`, otherwise return `false`.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# 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:
        def dfs(root, s):
            if root is None:
                return False
            s += root.val
            if root.left is None and root.right is None and s == targetSum:
                return True
            return dfs(root.left, s) or dfs(root.right, s)

        return dfs(root, 0)

Continue Practicing

#111 minimum depth of binary tree #116 populating next right pointers in each node #117 populating next right pointers in each node ii