Reference: LeetCode
Difficulty: Medium

## Problem

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Example:

## Analysis

Methods:

1. Recursion (Preorder traversal)
• Time: $O(N + Lh)$ where $L$ is the number of valid paths. 1 ms
• Visiting all nodes take $O(N)$.
• Creating $L$ valid paths, each one takes $h$ time to create.
• Space: $O(h + Lh) = O(Lh)$
• Note: We can make a new copy of list in each function call, but it takes a lot of space.
1. Iteration
• I tried preorder, inorder, bfs. All of them are difficult to implement because of the timing of recovering the path list.
• Finally, I add a map depthMap to record the depth of each node.

Time: $O(N + Lh)$. And recovering the path list takes time. 6 ms
Space: $O(N)$

## Code

### Recursion

Note:

• Remember to recover the path.
• Learn the way to make a new copy of list.
• Be careful of the generic type:
• Correct: LinkedList<List<Integer>> result = new LinkedList<>();
• Incorrect: LinkedList<LinkedList<Integer>> result = new LinkedList<>();
• The return type is List<List<Integer>>, which is not compatible with LinkedList<LinkedList<Integer>>.

### Iteration

Note:

• The order! Push into stack the right child first.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.