Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonFacebookGoogle

Path Sum II (All Root-to-Leaf Paths)

Choose your preparation mode4 modes available
📋
Problem

Imagine navigating a maze where you want to find all routes from the entrance to the exit that add up to a certain score. This problem is about finding all root-to-leaf paths in a binary tree whose node values sum to a target.

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. A leaf is a node with no children. Each path should be returned as a list of the node values, and the collection of paths should be returned as a list of lists.

The number of nodes in the tree is in the range [1, 5000]-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000000
Edge cases: Single node tree where node value equals targetSum → output is [[node.val]]Single node tree where node value does not equal targetSum → output is []Tree with negative values and targetSum that requires including negative nodes → output includes paths with negative values
</>
IDE
def pathSum(root: Optional[TreeNode], targetSum: int) -> List[List[int]]:public List<List<Integer>> pathSum(TreeNode root, int targetSum)vector<vector<int>> pathSum(TreeNode* root, int targetSum)function pathSum(root, targetSum)
def pathSum(root, targetSum):
    # Write your solution here
    pass
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // Write your solution here
        return new ArrayList<>();
    }
}
#include <vector>
using namespace std;

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
    // Write your solution here
    return {};
}
function pathSum(root, targetSum) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [[5,4,11]]Adding paths before confirming leaf node, missing last node in path.✅ Add path to results only if node.left == null and node.right == null.
Wrong: [[1]]Returning path even when single node value != targetSum.✅ Check if root.val == targetSum before adding path for single node tree.
Wrong: [[1,2]]Including partial paths that are not root-to-leaf.✅ Add paths only at leaf nodes, not intermediate nodes.
Wrong: []Pruning paths too early when negative values are present.✅ Do not prune paths based on partial sums; allow negative values in path sums.
Wrong: Partial or missing pathsGreedy pruning stops search after first valid path found.✅ Explore all paths fully using backtracking without early stopping.
✓
Test Cases
t1_01basic
Input{"root":[5,4,8,11,null,13,4,7,2,null,null,5,1],"targetSum":22}
Expected[[5,4,11,2],[5,8,4,5]]

There are two root-to-leaf paths where the sum is 22: 5->4->11->2 and 5->8->4->5.

t1_02basic
Input{"root":[1,2,3],"targetSum":4}
Expected[[1,3]]

Only one root-to-leaf path sums to 4: 1->3.

t2_01edge
Input{"root":[1],"targetSum":1}
Expected[[1]]

Single node tree where node value equals targetSum; path is just [1].

t2_02edge
Input{"root":[1],"targetSum":2}
Expected[]

Single node tree where node value does not equal targetSum; no valid paths.

t2_03edge
Input{"root":[1,-2,-3,1,3,-2,null,-1],"targetSum":-1}
Expected[[1,-2,1,-1]]

Tree with negative values; path 1->-2->1->-1 sums to -1.

t3_01corner
Input{"root":[1,2,3,4,5,6,7],"targetSum":10}
Expected[[1,2,4],[1,3,6]]

Multiple paths sum to 10; tests correct path collection without greedy pruning.

t3_02corner
Input{"root":[1,2,null,3,null,4,null,5],"targetSum":15}
Expected[[1,2,3,4,5]]

Deep single branch tests stack handling and correct sum calculation.

t3_03corner
Input{"root":[1,2,3],"targetSum":3}
Expected[[1,2]]

Tests confusion between 0/1 and unbounded path sums; only root-to-leaf paths allowed.

t4_01performance
Input{"_description":"n=5000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

Large tree with 5000 nodes tests O(N*L) DFS complexity; must complete within 2 seconds.

Practice

(1/5)
1. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total
medium
A. Line with 'if not node:' return statement
B. Line adding current_number to self.total
C. Line checking if node is leaf
D. Line calling dfs on node.right

Solution

  1. Step 1: Understand when sums should be added

    Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.
  2. Step 2: Identify incorrect addition

    Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum only at leaves fixes the bug [OK]
Hint: Add to total only at leaf nodes [OK]
Common Mistakes:
  • Adding partial path sums at non-leaf nodes
  • Not resetting total between calls
2. Suppose the problem is modified so that the binary tree nodes can be reused multiple times in the flattened linked list (i.e., nodes can appear multiple times). Which modification to the optimal flatten algorithm is necessary to handle this correctly?
hard
A. No change needed; the current in-place reverse preorder traversal works as is.
B. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates.
C. Modify the algorithm to clone nodes during traversal to allow multiple appearances.
D. Switch to a postorder traversal to ensure all duplicates are appended after processing children.

Solution

  1. Step 1: Understand reuse requirement

    Allowing nodes to appear multiple times means the original nodes cannot be simply rewired in-place without duplication.
  2. Step 2: Identify necessary modification

    Cloning nodes during traversal is required to create multiple instances, preserving original tree structure and allowing duplicates.
  3. Step 3: Why other options fail

    No change needed; the current in-place reverse preorder traversal works as is. fails because in-place rewiring destroys original nodes. Use a preorder traversal to collect nodes in a list and rebuild the linked list allowing duplicates. collects nodes but does not clone them. Switch to a postorder traversal to ensure all duplicates are appended after processing children. traversal order does not address duplication.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Cloning nodes enables multiple appearances in flattened list [OK]
Hint: Cloning nodes is needed for multiple appearances [OK]
Common Mistakes:
  • Assuming in-place rewiring supports duplicates
  • Collecting nodes without cloning leads to lost references
  • Changing traversal order alone does not solve duplication
3. Suppose the problem is modified so that you can rob the same node multiple times (i.e., nodes can be reused any number of times), but still cannot rob directly connected nodes simultaneously. Which modification to the algorithm is necessary to correctly solve this variant?
hard
A. Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse.
B. Use the same DFS with two-value return; no changes needed since adjacency constraints remain.
C. Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection.
D. Modify the DFS to allow revisiting nodes multiple times and use memoization keyed by node and robbing state.

Solution

  1. Step 1: Understand the reuse constraint

    Allowing multiple robberies per node breaks the tree structure assumption and simple one-time visit DFS.
  2. Step 2: Identify necessary algorithmic change

    We must track states including how many times a node is robbed and ensure adjacency constraints per robbery. Memoization keyed by node and robbing state prevents exponential recomputation.
  3. Step 3: Why other options fail

    Use the same DFS with two-value return; no changes needed since adjacency constraints remain. ignores reuse; Convert the tree into a graph and run a maximum weighted independent set algorithm with cycle detection. is overcomplicated and unnecessary since the structure is still a tree; Use a bottom-up DP that tracks counts of times each node is robbed to handle reuse. is vague and does not address adjacency constraints properly.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Memoization with extended state handles reuse and adjacency constraints [OK]
Hint: Reuse requires stateful memoization, not simple DFS [OK]
Common Mistakes:
  • Assuming original DFS suffices for reuse
  • Ignoring adjacency constraints when reusing nodes
4. Suppose the problem is modified so that paths can move both downwards and upwards (i.e., any connected path in the tree, not necessarily parent-to-child). Which of the following changes to the algorithm is necessary to correctly count all such paths?
hard
A. Convert the tree to an undirected graph and use DFS from every node with prefix sums, resetting counts after each start.
B. Use the brute force approach checking all paths from every node without prefix sums.
C. Use the same prefix sum DFS approach but run it twice: once from root down and once from leaves up.
D. Modify the prefix sum map to store sums for paths in both directions simultaneously during one DFS.

Solution

  1. Step 1: Understand path direction relaxation

    Allowing upward and downward moves means paths are any connected sequences, not just parent-to-child.
  2. Step 2: Model tree as undirected graph and run DFS from every node

    To count all paths, treat tree as undirected graph and run DFS from each node, using prefix sums and resetting counts to avoid cross-branch contamination.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Undirected DFS from every node with prefix sums counts all connected paths [OK]
Hint: Undirected graph DFS needed for arbitrary path directions [OK]
Common Mistakes:
  • Trying to reuse one-directional prefix sum DFS without modification
  • Assuming running DFS twice covers all paths
  • Trying to store both directions in one prefix sum map
5. Suppose the problem is modified so that node values can be negative integers, and the goal remains to sum all root-to-leaf numbers formed by concatenation (including negative signs). Which of the following changes to the algorithm is necessary to handle this correctly?
hard
A. Skip negative nodes since they break number formation
B. Continue using integer arithmetic with multiplication by 10, ignoring signs
C. Add absolute values of node.val to current_number to avoid sign issues
D. Use string concatenation of node values along the path and convert to integer at leaf nodes

Solution

  1. Step 1: Understand impact of negative values

    Integer arithmetic with multiplication by 10 assumes digits 0-9; negative signs break this assumption.
  2. Step 2: Identify correct approach

    Concatenating node values as strings preserves negative signs and digit order; convert to integer only at leaf nodes.
  3. Step 3: Confirm other options fail

    Ignoring signs or skipping negatives leads to incorrect sums or incomplete paths.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    String concatenation handles negative digits correctly [OK]
Hint: Use string concatenation for negative digits [OK]
Common Mistakes:
  • Assuming all digits are positive
  • Using arithmetic without sign handling
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard