Full lesson preview

Find all root-to-leaf paths with a given sum

Find all root-to-leaf paths in a binary tree where the sum of node values equals a target.

Python practice15 minTrees & Binary TreesIntermediateLast updated March 29, 2026

Problem statement

Given 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. A root-to-leaf path is a path starting from the root node and ending at any leaf node. Each path should be represented as a list of node values. If there are no such paths, return an empty list. The order of returned paths should follow a left-to-right traversal (i.e., explore left subtree before right subtree).

Task

Given the root of a binary tree and an integer target sum, return all root-to-leaf paths where each path's sum equals the target.

Examples

Example: Two paths

Input

root = [5,4,8,11,None,13,4,7,2,None,None,5,1], targetSum = 22

Output

[[5, 4, 11, 2], [5, 8, 4, 5]]

There are two root-to-leaf paths that sum to 22: 5->4->11->2 and 5->8->4->5.

Input format

The function receives two arguments: root (TreeNode or None) and targetSum (int). For test convenience, trees are built from level-order lists using build_tree(list).

Output format

Return a list of lists of integers. Each inner list represents a root-to-leaf path whose values sum to targetSum.

Constraints

- Node values can be negative, zero, or positive integers. - The number of nodes in the tree is in the range [0, 5000]. - Paths must be root-to-leaf (cannot stop at non-leaf nodes). - Use an algorithm with O(n) time complexity and O(h) auxiliary space (h = tree height) for recursion/stack.

Samples

Sample 1

Input

root = [1,2,3], targetSum = 5

Output

[]

No root-to-leaf path sums to 5.