Every Trail to the Target

MediumTrees

Problem

Given the root of a binary tree and an integer target, return every root-to-leaf trail whose values sum to target. Each trail is the list of values from root to leaf.

List the trails in the order their leaves appear from left to right.

Example 1

Input:
root = [5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1], target = 22
Output:
[[5, 4, 11, 2], [5, 8, 4, 5]]

Example 2

Input:
root = [1, 2, 3], target = 5
Output:
[]

Constraints

  • 0 ≤ number of nodes ≤ 5000
  • Tree height ≤ 500
  • -1000 ≤ node.val ≤ 1000
  • -1000 ≤ target ≤ 1000

Hint

Show the first hint

You need the whole trail, not only its sum. How do you keep the current trail without copying it at every node?

Walkthrough

How to approach it

01Clarify before coding

  • Must trails end at leaves? Yes.
  • Can two trails have identical values? Yes, list both (they end at different leaves).
  • What order? Left-to-right by leaf, which a left-first DFS gives naturally.

02Brute force

Pass a fresh copy of the trail into every recursive call and check at the leaves.

Cost: O(n · h) time and memory spent copying at every node, even for trails that never match.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.