Path Sum II

Interview Problem Interview Medium Choose / Explore / Unchoose Array Binary Tree

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.pathSum(root, targetSum). Return every root-to-leaf value path summing to targetSum in left-to-right DFS order.

Starter code

class Solution:
    def pathSum(self, root, targetSum):
        pass

Test cases

two-paths

{
  "args": [
    {
      "$type": "binary-tree",
      "values": [
        5,
        4,
        8,
        11,
        null,
        13,
        4,
        7,
        2,
        null,
        null,
        5,
        1
      ]
    },
    22
  ]
}

Expected: [[5,4,11,2],[5,8,4,5]]

Wizard outline

Step 1: Initialize Solution.pathSum
Replace the empty starter with the first real state owned by Solution.pathSum. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Two Paths case
Complete the readable core algorithm for one representative Interview case. Append before descent, copy a valid leaf path, and pop during backtracking.
Step 4: Harden the Nonleaf Match boundary
Repair the reviewed boundary and pass the complete submission contract. The path contains exactly the root-to-current values and remaining target subtracts their prefix. Therefore a leaf matches exactly when its value equals the remainder, and backtracking enumerates every root-to-leaf path once.

Footguns and prerequisites

A matching partial sum at a non-leaf does not qualify as a root-to-leaf path.
trees and graphs
recursion and backtracking

Reviewed references

LeetCode 113 — Path Sum II

Practice prerequisites

Carry State Through Tree DFS(opens in a new tab)
Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing path sum two as a complete Interview Problem.

Recommended approach and implementation

DFS while maintaining a path and remaining target. At a leaf with matching value, append a copy; pop after exploring both children.

Why it works: The path contains exactly the root-to-current values and remaining target subtracts their prefix. Therefore a leaf matches exactly when its value equals the remainder, and backtracking enumerates every root-to-leaf path once.

class Solution:
    def pathSum(self, root, targetSum):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        paths = []
        path = []
        def visit(node, remaining):
            if node is None: return
            path.append(node.val)
            if node.left is None and node.right is None and node.val == remaining:
                paths.append(path[:])
            else:
                visit(node.left, remaining - node.val)
                visit(node.right, remaining - node.val)
            path.pop()
        visit(root, targetSum)
        return paths