Skip to main content
Talentd

Path Sum II - Solution & Explanation

MediumBacktrackingTreeDepth-First SearchBinary Tree16 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: Given a binary tree and a target sum, return all root-to-leaf paths where the sum of node values equals the target. A path must start at the root and end at a leaf node, and you need to return every valid path.

Approach 1: Recursive Depth-First Search with Backtracking (O(n) time, O(h) space)

This approach performs a depth-first traversal from the root while maintaining the current path and remaining sum. At each node, append the node value to the path and subtract it from the remaining target. When a leaf node is reached and the remaining sum becomes zero, copy the current path into the result list. Backtracking is critical: after exploring a node’s children, remove the node from the path so the same list can be reused for other branches. Each node is visited once, giving O(n) traversal time where n is the number of nodes, while the recursion stack uses O(h) space where h is the tree height. This technique combines depth-first search with backtracking to efficiently explore every root-to-leaf path.

Approach 2: Iterative DFS with Stack (O(n) time, O(h) space)

An iterative variant replaces recursion with an explicit stack. Each stack entry stores the current node, the remaining sum, and the path taken so far. Start by pushing the root node and its value. Pop nodes from the stack, update the path and remaining sum, and push child nodes with updated state. When a leaf node is encountered and the remaining sum equals the node value, add the path to the result list. The traversal order still mimics DFS but avoids recursion, which can be helpful in environments with limited recursion depth. The algorithm still visits every node once, resulting in O(n) time complexity and O(h) auxiliary space for the stack in a balanced binary tree.

Recommended for interviews: Recursive DFS with backtracking is the expected solution. Interviewers want to see that you can track a path, update a running sum, and undo state changes when returning from recursion. The iterative stack version demonstrates deeper understanding of DFS mechanics, but the recursive version is usually faster to implement and easier to reason about during an interview.

Approach 1: Recursive Depth-First Search

Using a recursive DFS, traverse each path from root to leaf, maintaining the current path and its corresponding sum. When a leaf is reached, check if the path's sum matches the targetSum. Use backtracking to explore all paths.

We use a helper function, dfs, to recursively explore paths. We store current paths and their sums in arrays to keep track of potential solutions. When a solution is found at a leaf node, it is added to the result set, and backtracking ensures all paths are checked.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), where N is the number of nodes in the tree.

Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Try this approach in the editor →

Approach 2: Iterative Depth-First Search with Stack

An iterative approach using a stack can also be used for this problem. We maintain stacks that parallel traditional DFS traversal with added structures to track path and cumulative sum states for efficient exploration of all feasible root-to-leaf paths.

This C++ solution employs a stack to simulate DFS traversal iteratively. The stack holds node, cumulative sum, and path data. As each node is processed, we check for valid paths and update the result list accordingly. Paths are extended by exploring left and right children, augmented by the current node value.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(N), as each node is processed exactly once.

Space Complexity: O(N), since results and stack can store all nodes during worst-case full-tree traversal.

Try this approach in the editor →

Approach 3: DFS

We start from the root node, recursively traverse all paths from the root node to the leaf nodes, and record the path sum. When we traverse to a leaf node, if the current path sum equals targetSum, then we add this path to the answer.

The time complexity is O(n^2), where n is the number of nodes in the binary tree. The space complexity is O(n).

Code

PythonJavaC++GoRustJavaScript

Python

Java

C++

Go

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Depth-First Search

Time Complexity: O(N), where N is the number of nodes in the tree.

Space Complexity: O(H), where H is the height of the tree, due to the recursion stack.

Iterative Depth-First Search with Stack

Time Complexity: O(N), as each node is processed exactly once.

Space Complexity: O(N), since results and stack can store all nodes during worst-case full-tree traversal.

DFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive DFS with BacktrackingO(n)O(h)Best general solution for exploring all root-to-leaf paths in a binary tree.
Iterative DFS with StackO(n)O(h)Useful when avoiding recursion or when stack-based traversal is preferred.

Video Solution

Path Sum II - LeetCode 113 Python • Deepti Talesra • 7,782 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Path Sum II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Paths

Next

Path Sum