This practice workspace is built for desktop. Open it on a larger screen to start solving.

Path Sum II

Depth-First Search·Medium

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 leaf is a node with no children.

For determinism, the returned list of paths must be sorted lexicographically — i.e. compare paths element-wise as if they were sequences. Two valid solutions might emit paths in different traversal orders, so the test harness fixes the ordering.

Input convention. Level-order array with null for missing children.

Examples

Input: values = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

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

Input: values = [1,2,3], targetSum = 5

Output: []

Input: values = [], targetSum = 0

Output: []

Constraints

The number of nodes is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

00:00Preview Mode (Read Only)

Loading editor…

Tests

Preview Mode

This is a read-only preview of DSAMind's AI coaching. Sign up to get custom feedback on your own solution.

Passed32 ms

First attempt — retry to track metric movement here.

Your approach

Pattern:Depth-First Search
Time:O(N)
Space:O(1)

Complete approach — pattern and complexity both named.

Coach

What you got right

You correctly matched the sorted input requirement and implemented a linear-time scan using two pointers.

Where it diverged

No divergence detected. The code correctly aligns with the stated approach.

Next attempt: focus on

Try solving related sliding window problems to build familiarity with two-pointer variants.

Signals

No signals fired — clean run, you stayed in flow.