113. Path Sum II

Quick Identifier

Topic: trees
Pattern: Tree DFS + backtracking and DFS / backtracking
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Apple
Frequency: High
LeetCode: 113

Quick Sights

Time Complexity: O(n * h) in the worst case when copying valid paths from the optimal approach.
Space Complexity: O(h) recursion stack plus output from the optimal approach.
Core Mechanism: Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values along the path equals targetSum. Each path should be a list of the node values from root to leaf.

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of node values along the path equals targetSum. Each path should be a list of the node values from root to leaf.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

Collect all qualifying paths, not only existence
Root-to-leaf constraint → recursion naturally tracks prefix sum
Backtracking: push value going down, pop when unwinding to reuse one slice/list

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — copy path slice at every step — O(n²) worst copying cost.
Better / optimal — single mutable path buffer + append/pop — O(n²) worst output size, O(h) active path storage — one DFS with backtracking.

Optimal Solution

Go

package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func pathSum(root *TreeNode, targetSum int) [][]int {
	result := [][]int{}
	path := []int{}
	var walk func(*TreeNode, int)
	walk = func(node *TreeNode, remaining int) {
		if node == nil {
			return
		}
		remaining -= node.Val
		path = append(path, node.Val)
		if node.Left == nil && node.Right == nil {
			if remaining == 0 {
				copied := make([]int, len(path))
				copy(copied, path)
				result = append(result, copied)
			}
		} else {
			walk(node.Left, remaining)
			walk(node.Right, remaining)
		}
		path = path[:len(path)-1]
	}
	walk(root, targetSum)
	return result
}

JavaScript

class TreeNode {
	constructor(val = 0, left = null, right = null) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

function pathSum(root, targetSum) {
	const result = [];
	const path = [];
	function walk(node, remaining) {
		if (node === null) {
			return;
		}
		remaining -= node.val;
		path.push(node.val);
		if (node.left === null && node.right === null) {
			if (remaining === 0) {
				result.push([...path]);
			}
		} else {
			walk(node.left, remaining);
			walk(node.right, remaining);
		}
		path.pop();
	}
	walk(root, targetSum);
	return result;
}