Print root to leaf path in BT
MediumAppend on the way down, remove on the way back
Problem
Print all root-to-leaf paths in a binary tree.
DFS carrying the current path; when you hit a leaf, record the whole path.
The idea
Carry the current path as you descend and record it whenever you reach a leaf. Removing the node from the path as the recursion returns is what lets the same list be reused across every branch.
The trick
- Append, recurse, then pop — classic backtracking.
- A leaf is a node with no children at all, not just one missing child.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — [1,2,3,null,5] Values: 1, 2, 3, 5.
1dfs(node, path):2 path.push(node)3 if leaf: output path4 else dfs(left); dfs(right)5 path.pop()Input
- array
- [1, 2, 3, 5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- tree = [1,2,3,null,5]
- Output:
- [[1, 2, 5], [1, 3]]
- Explanation:
- Every path from root down to a leaf.
Example 2
- Input:
- tree = [1,2,3]
- Output:
- [[1, 2], [1, 3]]
- Explanation:
- [[1,2],[1,3]].
Example 3
- Input:
- tree = [1]
- Output:
- [[1]]
- Explanation:
- [[1]].
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.