How do you approach Path Sum?

Think recursively: a path of sum S through a node needs a path of sum S - node.val through one of its children.

What is the time complexity of Path Sum?

Time complexity: O(n) - each node visited once. Space complexity: O(h) recursion depth.

What are common mistakes on Path Sum?

Handling the null node deep in the recursion instead of as the first base case. Returning early from a subtree when the answer needs both sides explored. Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

gitGood.dev

← Back to problems

Path Sum

EasyData Structures

Description

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. **Note:** The tree is given as a level-order array where the node at index `i` has its left child at index `2*i + 1` and its right child at index `2*i + 2`, with `null` for missing nodes (trailing positions may be omitted). For example, `[5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, null, null, 1]` represents: ``` 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 ``` The path 5 -> 4 -> 11 -> 2 sums to 22.

Example 1

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

Output: true

Explanation: The root-to-leaf path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2

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

Output: false

Explanation: The two root-to-leaf paths sum to 3 and 4.

Example 3

Input: root = [], targetSum = 0

Output: false

Explanation: An empty tree has no root-to-leaf path.

Constraints

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

Path Sum: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Think recursively: a path of sum S through a node needs a path of sum S - node.val through one of its children.
Subtract the node's value from the remaining target as you descend; at a leaf, check whether the remainder is exactly 0.
Careful: the check must happen only at leaves (no children). Reaching 0 at an internal node doesn't count, and node values can be negative, so you can't prune early.

The optimal approach

Show the approach: DFS with Remaining Sum

Recurse down the tree, subtracting each node's value from the remaining target. When you reach a leaf, the path is valid iff the remainder is exactly zero. The check must be done at leaves only - and since values may be negative, you cannot stop early when the remainder goes below zero.

Time: O(n) - each node visited once
Space: O(h) recursion depth

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.

← Back to problems

Path Sum

EasyData Structures

Description

Example 1

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

Output: true

Explanation: The root-to-leaf path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2

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

Output: false

Explanation: The two root-to-leaf paths sum to 3 and 4.

Example 3

Input: root = [], targetSum = 0

Output: false

Explanation: An empty tree has no root-to-leaf path.

Constraints

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

Path Sum: approach, complexity and pitfalls

An easy trees problem, graded against 7 test cases (4 of them hidden).

The pattern: Trees

Recursive traversal of binary trees and BSTs - depth, validation, and path problems.

Reach for it when you see: A TreeNode input, or anything about depth, ancestry, or in-order ordering.

More Treesproblems →

If you are stuck

Show the 3-step hint ladder

Think recursively: a path of sum S through a node needs a path of sum S - node.val through one of its children.
Subtract the node's value from the remaining target as you descend; at a leaf, check whether the remainder is exactly 0.
Careful: the check must happen only at leaves (no children). Reaching 0 at an internal node doesn't count, and node values can be negative, so you can't prune early.

The optimal approach

Show the approach: DFS with Remaining Sum

Time: O(n) - each node visited once
Space: O(h) recursion depth

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Negative numbers. The suite includes negative values. Running-sum, min/max seeding and any "initialise to zero" step need to handle them.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Trees mistakes

These apply to the pattern as a whole, not just this problem.

Handling the null node deep in the recursion instead of as the first base case.
Returning early from a subtree when the answer needs both sides explored.
Confusing height with depth. One counts up from the node, the other down from the root, and the off-by-one is silent.