{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Path Sum II – Solution & Complexity

Interview solutions
/
Path Sum II

Solution Walkthrough

  1. Step 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. Step 2: Build the Algorithm

    Advance one state transition at a time. Mark or update state before exploring dependent work.

  3. Step 3: Check Edge Cases

    Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

  4. Step 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.

    def path_sum_ii(root: TreeNode, targetSum: int) -> list[list[int]]:
    result = []
    path = []

    def dfs(node, remaining):
        if node is None:
            return
        path.append(node.val)
        remaining -= node.val
        if node.left is None and node.right is None and remaining == 0:
            result.append(list(path))
        else:
            dfs(node.left, remaining)
            dfs(node.right, remaining)
        path.pop()

    dfs(root, targetSum)
    return result

FAQ

See also

Practice Path Sum II online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Maximum Path Sum solution (hard)Binary Tree Postorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?