113. Path Sum II

At a Glance

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

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.

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}