EasyBinary TreeRecursionDepth-First Search

Path Sum

1 approach, code in every language

You are given the root of a binary tree and an integer target. Determine whether the tree contains any root-to-leaf path whose node values add up exactly to the target. A leaf is a node with no children.

Return true if such a path exists and false otherwise. An empty tree contains no path and should return false.

Example 1

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

Output: true

The path 5 -> 4 -> 11 -> 2 sums to 22, so a qualifying root-to-leaf path exists.

Example 2

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

Output: false

The only root-to-leaf sums are 1+2=3 and 1+3=4, neither of which equals 5.

Constraints

The number of nodes is in the range [0, 5 * 10^3]
-10^3 ≤ Node.val ≤ 10^3
-10^3 ≤ target ≤ 10^3

Recursive Remaining-Sum

Subtract the current node's value from the target and recurse into children; at a leaf, check whether the remaining amount equals the leaf's value.

Loading animation…

Intuition

Instead of accumulating a running total on the way down, we shrink the target by each node value we pass through. This reframes the question at every node as: does one of my subtrees contain a root-to-leaf path summing to the reduced target? A leaf answers directly by comparing its own value against what remains. Because the recursion only reports true when it actually reaches a leaf with an exact match, we never mistakenly count a partial path.

Algorithm walkthrough

1If the current node is null, there is no path here, so return false.
2If the node is a leaf, return whether the target equals the node's value.
3Otherwise compute the remaining amount as target minus the node's value.
4Recurse into the left and right children with this remaining amount.
5Return true if either subtree reports a valid path; the answer bubbles up to the root.

Implementation

# 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:
            return targetSum == root.val
        remaining = targetSum - root.val
        return self.hasPathSum(root.left, remaining) or self.hasPathSum(root.right, remaining)

Time

O(n) because each node is visited once

Space

O(h) for the recursion stack, where h is the tree height

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

A Branch Whose Loads Add Up is our own problem on the technique behind Path Sum: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free