Path Sum II
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return every root-to-leaf path whose values add up to the target sum.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Carry the remaining sum down as you go. What must it be at a leaf?
- Hint 2Keep one shared path list: add the node before going deeper, remove it after.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A trekking trail map where every junction has a cost. You have a budget of exactly 22. Walk from the base camp down every trail, writing the junctions you pass on a notepad and subtracting each cost from your budget. At a dead end (a leaf) with exactly zero budget left, copy your notepad into the answer. Then walk back one junction, crossing it off the notepad, and try the next trail.
- The obvious way
No cheaper way exists; every root-to-leaf path may need checking: O(n) nodes plus copying the answers.
- The key insight
Walk down the tree subtracting each node's value from the remaining target and pushing the node on the path. At a leaf, if the remaining target is now zero, save a COPY of the path. Always pop the node when returning, so the shared path is correct for the next branch (backtracking).
- The algorithm
- Start with an empty path and the full target.
- At a node: add it to the path and subtract its value from the remaining target.
- At a leaf with 0 remaining: save a copy of the path.
- Visit both children, then remove this node from the path before returning.
Watch it run
Exampletree = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], target = 22
Walk 5 -> 4 -> 11 -> 7. Budget left: 22 - 5 - 4 - 11 - 7 = -5. A leaf with a wrong total: not saved. Step back.
path 5, 4, 11 (7 removed)
Where people slip
- Save a COPY of the path (list(path)); saving the shared list itself would be emptied by the backtracking.
- Only count a path at a LEAF; stopping at an inner node with the right total is wrong.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def path_sum(root, target):
answers = []
path = [] # the notepad of junctions passed
def walk(node, remaining):
if node is None:
return
path.append(node.val)
remaining -= node.val
if node.left is None and node.right is None and remaining == 0:
answers.append(list(path)) # save a COPY
walk(node.left, remaining)
walk(node.right, remaining)
path.pop() # backtrack: cross it off the notepad
walk(root, target)
return answersNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.