Path Sum II

MediumTreesbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree and an integer targetSum, find every **root-to-leaf** path whose node values add up to exactly targetSum. A leaf is a node with no children; a path must start at the root and end at a leaf. Return each path as a list of the node values from root to leaf. The paths themselves may be returned in **any order**, but each path's values must be listed root first. If no path matches (or the tree is empty), return []. Use a depth-first search with backtracking so each path list is built incrementally.

Examples

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]]
5+4+11+2 = 22 and 5+8+4+5 = 22; no other root-to-leaf path sums to 22.
Input: root = [1,2,3], targetSum = 5
Output: []
The two paths sum to 3 and 4.

Constraints

  • 0 <= number of nodes <= 5000
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems