This problem requires tracking the path state during traversal to capture all valid root-to-leaf sequences summing to targetSum. Backtracking ensures that paths are explored and reverted correctly to avoid incorrect combinations. Using depth-first search, we can recursively traverse nodes while maintaining a running sum and path list, collecting results only when leaf nodes meet the sum requirement.
Problem Statement
Given a binary tree root and an integer targetSum, identify all root-to-leaf paths where the sum of node values equals targetSum. Each path should be represented as a list of integers reflecting node values along that path.
A root-to-leaf path starts at the root and ends at a leaf, which has no children. Return all possible paths satisfying the sum condition, maintaining order from root to leaf. For example, root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22, yields [[5,4,11,2],[5,8,4,5]].
Examples
Example 1
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
There are two paths whose sum equals targetSum: 5 + 4 + 11 + 2 = 22 5 + 8 + 4 + 5 = 22
Example 2
Input: root = [1,2,3], targetSum = 5
Output: []
Example details omitted.
Example 3
Input: root = [1,2], targetSum = 0
Output: []
Example details omitted.
Constraints
- The number of nodes in the tree is in the range [0, 5000].
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
Solution Approach
Depth-First Search with Path Tracking
Use DFS to traverse the binary tree, maintaining a current path list and running sum. When a leaf node is reached, check if the sum equals targetSum, and if so, append a copy of the path to the results.
Backtracking to Explore All Paths
After visiting a node, recursively explore its children. Once both children are processed, remove the node from the current path to backtrack and explore alternative paths, ensuring no leftover state affects other paths.
Handle Edge Cases and Empty Trees
Ensure the function handles null roots, single-node trees, and paths where no combination meets the target. Early return for empty trees prevents unnecessary recursion and preserves correct path collection.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(N^2) in the worst case for a skewed tree because copying the path takes O(N) per leaf, with N nodes. Space complexity is O(N) for recursion stack and path storage.
What Interviewers Usually Probe
- Asks about recursive vs iterative DFS approaches for path tracking.
- Questions about handling negative values in node sums or targetSum.
- Wants explanation on why backtracking is essential to avoid incorrect path accumulation.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to backtrack and remove the last node, corrupting future paths.
- Returning paths before reaching leaf nodes, which violates root-to-leaf definition.
- Not handling empty trees or single-node cases properly, leading to runtime errors.
Follow-up variants
- Return only the first valid path instead of all paths.
- Modify the problem to find paths summing to a target in a n-ary tree instead of binary tree.
- Count the number of paths instead of returning the path lists.
How GhostInterview Helps
- Automatically structures DFS and backtracking code to track path state efficiently.
- Highlights edge cases like empty trees and single-node trees to avoid runtime errors.
- Generates optimized recursive solutions with proper path copying to prevent contamination between paths.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy for solving Path Sum II?
Use depth-first search combined with backtracking to track all root-to-leaf paths and validate their sums against targetSum.
How does backtracking help in this problem?
Backtracking ensures that after exploring a path, the last node is removed so alternative paths can be explored without carrying over previous state.
Can Path Sum II be solved iteratively?
Yes, using a stack to simulate DFS while storing current paths and running sums, but recursive DFS with backtracking is often simpler.
What are common mistakes when implementing Path Sum II?
Common mistakes include not removing nodes after recursion, checking sums before reaching leaves, or mishandling null trees.
Does negative values in nodes affect the approach?
No, DFS and backtracking handle negative values naturally as sums are evaluated at leaf nodes without assumptions about positivity.
Need direct help with Path Sum II instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Path Sum II from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find all root-to-leaf paths in a binary tree using DFS and backtracking, constructing strings for each complete path efficiently.
Open problem page#988 Smallest String Starting From LeafDetermine the lexicographically smallest string from a leaf to root using binary-tree traversal and careful state tracking.
Open problem page#112 Path SumDetermine 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.
Open problem page