How do you solve Path Sum II on LeetCode?

Path Sum II (LeetCode #113) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(h) space complexity. Key insight: Paths are explored using DFS, which allows us to backtrack efficiently.

What is the brute force solution for Path Sum II?

The brute force approach for Path Sum II is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we explore all possible paths from the root to each leaf node and calculate the sum of the node values along each path. If the sum matches the targetSum, we store that path. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Path Sum II?

Path Sum II uses the following concepts: Backtracking, Tree, Depth-First Search, Binary Tree. The recommended patterns to study are: Backtracking, Depth-First Search.

What are the interview tips for Path Sum II?

Explain your thought process clearly as you code. Make sure to handle edge cases, such as an empty tree. Discuss the trade-offs between different approaches.

What are common mistakes when solving Path Sum II?

Not checking if the node is null before accessing its properties. Forgetting to backtrack by removing the last node from the current path.

#113

Path Sum II

Medium

BacktrackingTreeDepth-First SearchBinary TreeBacktrackingDepth-First Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(h)

💡

Intuition

Time O(n)Space O(h)

This approach uses Depth-First Search (DFS) to explore paths while maintaining the current sum. We prune paths early if the current sum exceeds targetSum, making it more efficient than the brute force method.

⚙️

Algorithm

3 steps

1Step 1: Start from the root and traverse the tree using DFS, maintaining the current path and sum.
2Step 2: If a leaf node is reached and the current sum equals targetSum, add the current path to the result.
3Step 3: If the current sum exceeds targetSum, backtrack immediately to avoid unnecessary calculations.

solution.py25 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def pathSum(self, root: TreeNode, targetSum: int):
10        def dfs(node, currentPath, currentSum):
11            if not node:
12                return
13            currentPath.append(node.val)
14            currentSum += node.val
15            if not node.left and not node.right:
16                if currentSum == targetSum:
17                    result.append(list(currentPath))
18            else:
19                dfs(node.left, currentPath, currentSum)
20                dfs(node.right, currentPath, currentSum)
21            currentPath.pop()
22
23        result = []
24        dfs(root, [], 0)
25        return result

ℹ

Complexity note: The time complexity is O(n) because we visit each node exactly once. The space complexity is O(h) due to the recursion stack, where h is the height of the tree.

1Paths are explored using DFS, which allows us to backtrack efficiently.
2Checking if a node is a leaf helps in determining if we should add the path to the result.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.