Path Sum II – Solution & Complexity
Solution Walkthrough
1. Recognize the Pattern
The key pattern is: DFS with backtracking — push the current node onto a shared path buffer, recurse, then pop it back off after both children have been explored, so every leaf sees the exact path that led to it.
2. Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
3. Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
4. Solution and Complexity
Time: O(n^2) worst case — every node is visited once (O(n)), and each of up to O(n) valid paths can be up to O(n) long to copy into the result. Space: O(n) for the recursion stack and the current path buffer, not counting the output.
All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.
