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

📋

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
}

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

Focus on handling edge cases like single nodes and negative values correctly.

Watch out for common pitfalls like greedy pruning and incorrect leaf checks.

Prepare for performance challenges by optimizing your DFS and backtracking.

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]]

⏱ Performance - must finish in 2000ms

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

💡 Think about traversing all root-to-leaf paths using DFS.

💡 Use backtracking to keep track of the current path and sum.

💡 Add the current path to results only if at a leaf and sum equals targetSum.

Why it failed: Failed to find all valid root-to-leaf paths summing to targetSum. Fix by ensuring you check sum only at leaf nodes and backtrack properly.

✓ Correctly finds all root-to-leaf paths with sum equal to targetSum.

t1_02basic

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

Expected[[1,3]]

⏱ Performance - must finish in 2000ms

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

💡 Check all root-to-leaf paths and sum their values.

💡 Remember to only add paths when you reach leaf nodes.

💡 Backtrack after exploring each child to explore other paths.

Why it failed: Incorrect output due to missing leaf check or incorrect sum calculation. Fix by verifying leaf condition and sum at each path end.

✓ Correctly identifies the single valid root-to-leaf path summing to targetSum.

t2_01edge

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

Expected[[1]]

⏱ Performance - must finish in 2000ms

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

💡 Consider the simplest tree with only one node.

💡 Check if the single node's value equals targetSum.

💡 Return [[node.val]] if equal, else return [].

Why it failed: Fails to handle single node trees correctly; fix by checking if root is leaf and its value equals targetSum.

✓ Handles single node tree correctly when node value equals targetSum.

t2_02edge

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

Expected[]

⏱ Performance - must finish in 2000ms

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

💡 Check if single node's value matches targetSum.

💡 If not, no paths should be returned.

💡 Return empty list if no root-to-leaf path sums to targetSum.

Why it failed: Incorrectly returns a path when single node value != targetSum; fix by validating sum at leaf nodes.

✓ Correctly returns empty list when no path sums to targetSum.

t2_03edge

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

Expected[[1,-2,1,-1]]

⏱ Performance - must finish in 2000ms

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

💡 Remember node values can be negative.

💡 Sum paths carefully including negative values.

💡 Do not prune paths prematurely; negative values can lead to valid sums.

Why it failed: Fails to handle negative values correctly; fix by allowing sums to include negative nodes and not pruning early.

✓ Correctly finds paths including negative values summing to targetSum.

t3_01corner

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

Expected[[1,2,4],[1,3,6]]

⏱ Performance - must finish in 2000ms

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

💡 Avoid greedy pruning that stops after first valid path.

💡 Explore all root-to-leaf paths fully.

💡 Backtrack properly to collect all valid paths.

Why it failed: Greedy pruning caused missing valid paths; fix by exploring all paths without early stopping.

✓ Correctly collects all root-to-leaf paths summing to targetSum.

t3_02corner

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

Expected[[1,2,3,4,5]]

⏱ Performance - must finish in 2000ms

Deep single branch tests stack handling and correct sum calculation.

💡 Check deep recursion and path tracking.

💡 Ensure path is copied correctly when adding to results.

💡 Verify sum calculation at leaf nodes.

Why it failed: Incorrect path due to shallow copy or incorrect sum at leaf; fix by copying path list when adding to results.

✓ Correctly handles deep single branch and sums.

t3_03corner

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

Expected[[1,2]]

⏱ Performance - must finish in 2000ms

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

💡 Remember only root-to-leaf paths count, no repeated nodes.

💡 Do not consider partial paths that are not root-to-leaf.

💡 Check leaf condition before adding path.

Why it failed: Includes non-leaf paths or partial sums; fix by adding paths only at leaf nodes.

✓ Correctly restricts to root-to-leaf paths only.

t4_01performance

Input{"_description":"n=5000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Optimize DFS with pruning and backtracking.

💡 Avoid unnecessary copying of paths.

💡 Use iterative DFS or tail recursion if needed.

Why it failed: TLE due to exponential or inefficient DFS; fix by using pruning and efficient path tracking.

✓ Algorithm runs within time limits confirming O(N*L) complexity.

Practice

1. Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree: root=1, left=2, right=3, and node 2 has left child 4. What is the value of heights[root] after the traversal completes?

easy

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Trace heights for leaf nodes

   Node 4 is a leaf, so heights[4] = 1.

2. Step 2: Compute heights bottom-up

   Node 2 has left child 4 (height 1) and no right child (height 0), so heights[2] = 1 + max(1,0) = 2. Node 3 is leaf, heights[3] = 1. Root 1 has children heights 2 and 1, so heights[1] = 1 + max(2,1) = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Height of root is max height of subtrees plus one [OK]

Hint: Height of root equals max subtree height plus one [OK]

Common Mistakes:

• Forgetting to add 1 for current node height
• Mixing up left and right subtree heights
• Returning height instead of boolean balance

2. You need to convert a binary tree into a string and then reconstruct the exact same tree from that string. Which approach guarantees that the tree structure, including null children, is preserved and can be reconstructed efficiently?

easy

A. Use level order traversal (BFS) including null markers for missing children, then deserialize by reading nodes level by level.

B. Use a greedy traversal that records only node values without null markers, then reconstruct by inserting nodes in order.

C. Use dynamic programming to store subtree encodings and reconstruct from stored subtrees.

D. Use inorder traversal without null markers and reconstruct by assuming a balanced tree.

Solution

1. Step 1: Understand the need for null markers

   Without null markers, the tree structure cannot be uniquely reconstructed because missing children are ambiguous.

2. Step 2: Recognize BFS with null markers preserves structure

   Level order traversal with null markers records nodes level by level, capturing the exact shape of the tree, enabling correct deserialization.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Level order with null markers uniquely encodes tree structure [OK]

Hint: Null markers are essential to preserve tree shape [OK]

Common Mistakes:

• Ignoring null markers leads to ambiguous deserialization
• Assuming inorder traversal alone can reconstruct arbitrary trees
• Using greedy or DP approaches that don't preserve structure

3. What is the time complexity of the brute force approach that separately computes height for each node to check if a binary tree is balanced?

medium

A. O(n^2)

B. O(n)

C. O(n log n)

D. O(n h) where h is tree height

Solution

1. Step 1: Analyze height computation calls

   Height is computed recursively for each node, and each height call traverses subtree nodes.

2. Step 2: Calculate total calls

   For n nodes, height is called at each node, and each call can take O(n) in worst case, leading to O(n^2) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated height calls cause quadratic time [OK]

Hint: Repeated height calls cause O(n²) time [OK]

Common Mistakes:

• Assuming height calls are O(1) leading to O(n) time
• Confusing height with depth or tree height h
• Thinking O(n log n) due to balanced tree assumption

4. What is the time complexity of the optimal countNodes algorithm that uses binary search on the last level of a complete binary tree with n nodes?

medium

A. O(log n)

B. O(n)

C. O((log n)^2)

D. O(n log n)

Solution

1. Step 1: Analyze height and binary search

   Height h = O(log n). Binary search on last level does O(log n) steps.

2. Step 2: Combine existence checks

   Each existence check traverses height h = O(log n). Total time = O(log n) * O(log n) = O((log n)^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested log factors from height and binary search [OK]

Hint: Two nested log factors multiply to (log n)^2 [OK]

Common Mistakes:

• Confusing O(log n) with O((log n)^2)
• Assuming linear time due to traversal

5. What is the space complexity of the Morris Preorder Traversal approach for summing root-to-leaf numbers in a binary tree with n nodes?

medium

A. O(1) because Morris traversal uses threaded binary tree links without extra stack

B. O(n) due to recursion stack in DFS

C. O(h) where h is tree height due to implicit stack usage

D. O(n) because all nodes are visited and stored temporarily

Solution

1. Step 1: Identify space usage in Morris traversal

   Morris traversal modifies tree pointers temporarily to avoid recursion or explicit stack, so no extra stack space is used.

2. Step 2: Confirm no auxiliary data structures

   Only constant extra variables (pointers and counters) are used, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Morris traversal is known for O(1) space by threading tree [OK]

Hint: Morris traversal avoids recursion and stack [OK]

Common Mistakes:

• Confusing recursion stack with Morris traversal
• Assuming O(h) due to tree height