Path Sum II solution and explanation
Google
9 more videos on this problem
Path Sum II - LeetCode 113 PythonDeepti Talesra · 9:13 · 7K views
Leetcode - Path Sum II (Python)Timothy H Chang · 4:46 · 6K views
LEETCODE 113 (JAVASCRIPT) | PATH SUM IIAndy Gala · 12:56 · 3K views
[Java] Leetcode 113. Path Sum II [Binary Tree #13]Eric Programming · 8:44 · 2K views
Path Sum II - LeetCode 113 - JavaScriptAlgoJS · 7:31 · 1K views
Solving LeetCode 113 in JavaScript (Path Sum II)KA Education · 5:20 · 1K views
Path Sum II - LeetCode 113 - JavaScriptAlgoJS · 8:15 · 946 views
Path Sum II | LeetCode 113 | Coders CampCoders Camp · 7:15 · 626 views
LeetCode - 113. Path Sum II | DFS | JavaOrkhan Gasanov · 11:15 · 406 views
Leetcode 113: Path Sum II | Master Trees | Intuition and ApproachCode Concepts with Animesh · 15:20 · 401 views
The problem
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.
from typing import List, Optional
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(node, current_sum, path):
if not node:
return
current_sum += node.val
path.append(node.val)
if not node.left and not node.right and current_sum == targetSum:
result.append(list(path))
else:
dfs(node.left, current_sum, path)
dfs(node.right, current_sum, path)
path.pop()
result = []
dfs(root, 0, [])
return resultimport java.util.ArrayList;
import java.util.List;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, result);
return result;
}
private void dfs(TreeNode node, int sum, List<Integer> path, List<List<Integer>> result) {
if (node == null) return;
path.add(node.val);
if (node.left == null && node.right == null && sum == node.val) {
result.add(new ArrayList<>(path));
} else {
dfs(node.left, sum - node.val, path, result);
dfs(node.right, sum - node.val, path, result);
}
path.remove(path.size() - 1);
}
}#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
void dfs(TreeNode* root, int targetSum, vector<int>& path, vector<vector<int>>& result) {
if (!root) return;
path.push_back(root->val);
targetSum -= root->val;
if (!root->left && !root->right && targetSum == 0) {
result.push_back(path);
} else {
dfs(root->left, targetSum, path, result);
dfs(root->right, targetSum, path, result);
}
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> path;
dfs(root, targetSum, path, result);
return result;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var pathSum = function(root, targetSum) {
const result = [];
const path = [];
const dfs = (node, currentSum) => {
if (!node) return;
currentSum += node.val;
path.push(node.val);
if (!node.left && !node.right && currentSum === targetSum) {
result.push([...path]);
} else {
dfs(node.left, currentSum);
dfs(node.right, currentSum);
}
path.pop();
};
dfs(root, 0);
return result;
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void dfs(struct TreeNode* root, int targetSum, int currentSum, int* path, int pathIndex, int** result, int* returnSize, int** columnSizes) {
if (!root) return;
currentSum += root->val;
path[pathIndex++] = root->val;
if (!root->left && !root->right && currentSum == targetSum) {
result[*returnSize] = (int*)malloc(pathIndex * sizeof(int));
columnSizes[0][*returnSize] = pathIndex;
for (int i = 0; i < pathIndex; ++i) {
result[*returnSize][i] = path[i];
}
(*returnSize)++;
} else {
dfs(root->left, targetSum, currentSum, path, pathIndex, result, returnSize, columnSizes);
dfs(root->right, targetSum, currentSum, path, pathIndex, result, returnSize, columnSizes);
}
}
int** pathSum(struct TreeNode* root, int targetSum, int* returnSize, int** columnSizes) {
*returnSize = 0;
int** result = (int**)malloc(1000 * sizeof(int*));
*columnSizes = (int*)malloc(1000 * sizeof(int));
int* path = (int*)malloc(1000 * sizeof(int));
dfs(root, targetSum, 0, path, 0, result, returnSize, columnSizes);
free(path);
return result;
}using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
IList<IList<int>> result = new List<IList<int>>();
List<int> path = new List<int>();
Dfs(root, targetSum, path, result);
return result;
}
private void Dfs(TreeNode node, int sum, List<int> path, IList<IList<int>> result) {
if (node == null) return;
path.Add(node.val);
if (node.left == null && node.right == null && sum == node.val) {
result.Add(new List<int>(path));
} else {
Dfs(node.left, sum - node.val, path, result);
Dfs(node.right, sum - node.val, path, result);
}
path.RemoveAt(path.Count - 1);
}
}In this Python solution, we perform a DFS and track the path and its cumulative sum. Upon meeting both the leaf and sum conditions, we add the path to the result using list operations for copying and backtracking.
Time Complexity: O(N), where N represents the number of nodes.
Space Complexity: O(H), mainly for the recursion stack.
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.
#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
if (!root) return result;
stack<pair<TreeNode*, pair<int, vector<int>>>> stk;
stk.push({root, {root->val, {root->val}}});
while (!stk.empty()) {
auto [node, state] = stk.top(); stk.pop();
auto [currentSum, path] = state;
if (!node->left && !node->right && currentSum == targetSum) {
result.push_back(path);
}
if (node->right) {
path.push_back(node->right->val);
stk.push({node->right, {currentSum + node->right->val, path}});
path.pop_back();
}
if (node->left) {
path.push_back(node->left->val);
stk.push({node->left, {currentSum + node->left->val, path}});
path.pop_back();
}
}
return result;
}
};function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var pathSum = function(root, targetSum) {
if (!root) return [];
const result = [];
const stack = [[root, root.val, [root.val]]];
while (stack.length > 0) {
const [node, sum, path] = stack.pop();
if (node.left === null && node.right === null && sum === targetSum) {
result.push(path);
}
if (node.right) {
stack.push([node.right, sum + node.right.val, path.concat(node.right.val)]);
}
if (node.left) {
stack.push([node.left, sum + node.left.val, path.concat(node.left.val)]);
}
}
return result;
};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.
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.
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).
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) (ans [][]int) {
t := []int{}
var dfs func(*TreeNode, int)
dfs = func(root *TreeNode, s int) {
if root == nil {
return
}
s -= root.Val
t = append(t, root.Val)
if root.Left == nil && root.Right == nil && s == 0 {
ans = append(ans, slices.Clone(t))
}
dfs(root.Left, s)
dfs(root.Right, s)
t = t[:len(t)-1]
}
dfs(root, targetSum)
return
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(
root: Option<Rc<RefCell<TreeNode>>>,
paths: &mut Vec<i32>,
mut target_sum: i32,
res: &mut Vec<Vec<i32>>,
) {
if let Some(node) = root {
let mut node = node.borrow_mut();
target_sum -= node.val;
paths.push(node.val);
if node.left.is_none() && node.right.is_none() {
if target_sum == 0 {
res.push(paths.clone());
}
} else {
if node.left.is_some() {
Self::dfs(node.left.take(), paths, target_sum, res);
}
if node.right.is_some() {
Self::dfs(node.right.take(), paths, target_sum, res);
}
}
paths.pop();
}
}
pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> Vec<Vec<i32>> {
let mut res = vec![];
let mut paths = vec![];
Self::dfs(root, &mut paths, target_sum, &mut res);
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search | Time Complexity: O(N), where N represents the number of nodes. Space Complexity: O(H), mainly for 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS with Backtracking | O(n) | O(h) | Best general solution for exploring all root-to-leaf paths in a binary tree. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion or when stack-based traversal is preferred. |
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.