LeetCode 112 - Path Sum

LeetCode Problem 112

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

Solution

Problem Understanding

This problem asks us to determine whether a binary tree contains at least one valid root-to-leaf path whose node values add up to a given target sum.

A binary tree consists of nodes where each node can have a left child and a right child. Each node also stores an integer value. The input provides the root node of the tree and an integer called targetSum.

A root-to-leaf path means:

• The path must start at the root node.
• The path must end at a leaf node.
• A leaf node is a node with no left child and no right child.

The goal is to check whether there exists at least one such path where the sum of all node values along the path equals targetSum.

For example, suppose the tree contains the path:

5 -> 4 -> 11 -> 2

The sum is:

5 + 4 + 11 + 2 = 22

If targetSum = 22, then the answer is true.

An important detail is that the path must end at a leaf. A partial path that reaches the target sum before reaching a leaf does not count.

The constraints are relatively small:

• Up to 5000 nodes
• Node values can be negative
• Target sum can also be negative

Since the tree can contain negative numbers, we cannot rely on pruning strategies such as "stop when the sum becomes too large". Every valid path must be explored carefully.

Several edge cases are important:

• The tree may be empty. In that case, there are no root-to-leaf paths, so the answer is always false.
• A tree with a single node should return true if the node value equals targetSum.
• Negative values may cause sums to increase or decrease unpredictably.
• A matching sum at a non-leaf node must not be treated as success.

Approaches

Brute Force Approach

A brute-force strategy would generate every root-to-leaf path in the tree, compute the sum of each path, and then compare the result with targetSum.

One way to do this is:

1. Use DFS traversal to explore all paths.
2. Store the current path in an array.
3. Whenever a leaf node is reached, compute the sum of the path array.
4. Check whether the sum equals targetSum.

This works because every possible root-to-leaf path is examined. If any path has the required sum, the algorithm returns true.

However, this approach is inefficient because the path sum is recomputed repeatedly from scratch for every leaf node. If the tree is large, many overlapping calculations occur.

Key Insight for the Optimal Solution

The important observation is that we do not need to store entire paths or repeatedly recompute sums.

Instead, while traversing the tree, we can continuously subtract the current node's value from the remaining target sum.

Suppose we are currently at a node with value x.

If we still need a remaining sum of target, then after visiting this node we only need to check whether one of its children can provide:

target - x

When we finally reach a leaf node, we simply check whether the remaining sum equals the leaf's value.

This allows us to solve the problem using a clean recursive DFS traversal with no extra path storage.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N²) in worst case	O(H)	Recomputes path sums repeatedly
Optimal DFS	O(N)	O(H)	Processes each node once using running remaining sum

Here:

• N is the number of nodes.
• H is the height of the tree.

Algorithm Walkthrough

Optimal Depth-First Search Algorithm

1. Start traversal from the root node.

The root is the starting point of every valid root-to-leaf path. 2. Handle the empty tree case.

If root is None, return False immediately because no path exists. 3. Subtract the current node's value from the remaining target sum.

This converts the problem from:

"Can this subtree produce targetSum?"

into:

"Can one of the child paths produce the remaining sum?"

4. Check whether the current node is a leaf node.

A node is a leaf if:

node.left is None and node.right is None

5. If the current node is a leaf, compare its value with the remaining target.

If:

remaining_sum == node.val

then we found a valid root-to-leaf path, so return True. 6. Otherwise, recursively explore the left and right subtrees.

Pass the updated remaining sum:

targetSum - node.val

7. If either subtree returns True, propagate the result upward.

Since we only need one valid path, logical OR is sufficient. 8. If neither subtree contains a valid path, return False.

Why it works

At every recursive call, the algorithm maintains the invariant:

targetSum represents the remaining sum required from the current node to a leaf.

Each recursive step subtracts the current node's value, reducing the remaining requirement correctly.

When a leaf node is reached, the path is valid exactly when the leaf's value matches the remaining required sum. Since every root-to-leaf path is explored once, the algorithm is guaranteed to find a valid path if one exists.

Python 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

from typing import Optional

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if root is None:
            return False

        # Check leaf node
        if root.left is None and root.right is None:
            return root.val == targetSum

        remaining_sum = targetSum - root.val

        return (
            self.hasPathSum(root.left, remaining_sum)
            or self.hasPathSum(root.right, remaining_sum)
        )

The implementation follows the recursive DFS strategy directly.

The first condition handles the empty tree case. Since there are no nodes, no root-to-leaf path exists.

Next, the code checks whether the current node is a leaf. This is the termination condition of the recursion. At a leaf node, we simply compare the node value against the remaining target sum.

If the node is not a leaf, the algorithm subtracts the current node's value from targetSum. This produces the remaining sum required from the subtree.

Finally, the function recursively searches both subtrees. If either recursive call returns True, the entire function returns True.

The implementation is concise because the recursive structure naturally mirrors the tree structure.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func hasPathSum(root *TreeNode, targetSum int) bool {
    if root == nil {
        return false
    }

    // Check leaf node
    if root.Left == nil && root.Right == nil {
        return root.Val == targetSum
    }

    remainingSum := targetSum - root.Val

    return hasPathSum(root.Left, remainingSum) ||
        hasPathSum(root.Right, remainingSum)
}

The Go implementation is nearly identical to the Python version.

The main language-specific difference is the use of nil instead of None.

Go also uses pointers for tree nodes, so recursive calls naturally operate on subtree references.

Integer overflow is not a concern because the constraints are small enough to fit safely within Go's standard int type.

Worked Examples

Example 1

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

The valid path is:

5 -> 4 -> 11 -> 2

Step-by-step Trace

Current Node	Remaining Target Before Visit	Remaining Target After Visit	Leaf?	Result
5	22	17	No	Continue
4	17	13	No	Continue
11	13	2	No	Continue
7	2	-5	Yes	False
2	2	0	Yes	True

When the algorithm reaches node 2, the remaining target becomes 0, so a valid path exists.

Final answer:

true

Example 2

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

Possible paths:

1 -> 2 = 3
1 -> 3 = 4

Step-by-step Trace

Current Node	Remaining Target Before Visit	Remaining Target After Visit	Leaf?	Result
1	5	4	No	Continue
2	4	2	Yes	False
3	4	1	Yes	False

No valid path reaches sum 5.

Final answer:

false

Example 3

Input:
root = []
targetSum = 0

The root is None, so there are no root-to-leaf paths.

Final answer:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every node is visited at most once
Space	O(H)	Recursive call stack stores at most tree height

The DFS traversal processes each node exactly one time, leading to linear time complexity.

The space complexity comes from recursion depth. In the worst case of a skewed tree, the height can become N, producing O(N) recursion stack usage. In a balanced tree, the height is approximately O(log N).

Test Cases

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

s = Solution()

# Example 1
root1 = TreeNode(
    5,
    TreeNode(
        4,
        TreeNode(
            11,
            TreeNode(7),
            TreeNode(2)
        )
    ),
    TreeNode(
        8,
        TreeNode(13),
        TreeNode(4, None, TreeNode(1))
    )
)
assert s.hasPathSum(root1, 22) == True  # valid root-to-leaf path exists

# Example 2
root2 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)
assert s.hasPathSum(root2, 5) == False  # no path sums to 5

# Example 3
assert s.hasPathSum(None, 0) == False  # empty tree

# Single node equal to target
root3 = TreeNode(7)
assert s.hasPathSum(root3, 7) == True  # single-node valid path

# Single node not equal to target
root4 = TreeNode(7)
assert s.hasPathSum(root4, 10) == False  # single-node invalid path

# Negative values
root5 = TreeNode(
    -2,
    None,
    TreeNode(-3)
)
assert s.hasPathSum(root5, -5) == True  # handles negative sums correctly

# Path sum exists only at non-leaf
root6 = TreeNode(
    1,
    TreeNode(2),
    TreeNode(3)
)
assert s.hasPathSum(root6, 1) == False  # root alone is not a leaf

# Left-skewed tree
root7 = TreeNode(
    1,
    TreeNode(
        2,
        TreeNode(
            3,
            TreeNode(4)
        )
    )
)
assert s.hasPathSum(root7, 10) == True  # deep recursive traversal

# Right-skewed tree
root8 = TreeNode(
    1,
    None,
    TreeNode(
        2,
        None,
        TreeNode(3)
    )
)
assert s.hasPathSum(root8, 6) == True  # right-only traversal

# Multiple paths, only one valid
root9 = TreeNode(
    10,
    TreeNode(5, TreeNode(3), TreeNode(2)),
    TreeNode(12)
)
assert s.hasPathSum(root9, 22) == True  # valid path through right child

Test Case Summary

Test	Why
Example 1	Standard successful case
Example 2	Standard unsuccessful case
Empty tree	Verifies handling of None root
Single node equal target	Simplest valid tree
Single node unequal target	Simplest invalid tree
Negative values	Ensures negative arithmetic works
Matching sum at non-leaf	Confirms leaf requirement
Left-skewed tree	Tests deep recursion on left side
Right-skewed tree	Tests deep recursion on right side
Multiple paths	Ensures algorithm finds any valid path

Edge Cases

Empty Tree

An empty tree is represented by root = None. This case is easy to mishandle because some implementations may incorrectly treat a target sum of 0 as success.

However, the problem specifically requires a root-to-leaf path, and an empty tree contains no paths at all.

The implementation handles this immediately with:

if root is None:
    return False

Matching Sum Before Reaching a Leaf

A common mistake is returning True as soon as the running sum equals the target.

Consider:

    1
   /
  2

If targetSum = 1, the root alone matches the target, but the root is not a leaf. Therefore, the answer must still be False.

The implementation avoids this bug by checking the sum only when a leaf node is reached.

Negative Values

Because node values may be negative, the running sum can increase or decrease unpredictably.

For example:

-2 -> -3

produces:

-5

An incorrect optimization that stops traversal when the sum becomes "too small" or "too large" would fail on such inputs.

The implementation correctly explores all root-to-leaf paths regardless of intermediate sums.