Is Path Sum II easy or hard?

Path Sum II is considered a medium difficulty problem. The traversal itself is straightforward DFS, but the challenge comes from managing the path list correctly and applying backtracking so sibling branches do not reuse incorrect state.

How to solve Path Sum II in O(n)?

Perform a depth-first traversal starting from the root while maintaining the remaining target sum and the current path. Subtract the node value from the remaining sum as you go deeper. When you reach a leaf node and the remaining sum equals zero, record the path. Because each node is processed once, the traversal runs in O(n) time.

What is the best approach for Path Sum II?

Recursive depth-first search with backtracking is the most common solution. Traverse the tree while tracking the current path and remaining sum. When a leaf node is reached and the sum matches the target, store the path. This approach visits each node once and runs in O(n) time with O(h) recursion stack space.

What data structure is used in Path Sum II?

The core data structure is a binary tree. The solution typically uses recursion (call stack) or an explicit stack for DFS traversal, along with a dynamic list or array to track the current root-to-leaf path.

What is the time complexity of Path Sum II?

The traversal visits every node in the binary tree once, resulting in O(n) time complexity where n is the number of nodes. Additional work occurs when copying valid paths into the result list. The auxiliary space is O(h) for the recursion stack, where h is the height of the tree.

Path Sum II Python or Java solution approach?

Both Python and Java implementations usually follow the same recursive DFS pattern. Maintain a list representing the current path, subtract node values from the target during traversal, and backtrack after exploring each child. When a valid leaf path is found, copy the path into the result list.

Is Path Sum II asked at Google, Amazon, or Meta?

Path Sum II appears frequently in interviews that test tree traversal and recursion skills. Variants of the problem have been reported in interviews at Amazon, Google, Meta, and Microsoft because it evaluates DFS traversal, path tracking, and backtracking logic in binary trees.

Description Solution Video 9:13

113. Path Sum II

Medium62.6% acceptance10 companies

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. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []

Example 3:

Input: root = [1,2], targetSum = 0
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Asked at 10 companies

Arista Networks Flipkart Palo Alto Networks Microsoft Meta Bloomberg Tiktok

Google Amazon Oracle

Topics

9:13

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

113. Path Sum II

Asked at 10 companies

Topics

Similar problems